Reduce a given Binary Array to a single element by removal of Triplets
Given an binary array arr[] of size N, the task is to reduce the array to a single element by the following two operations:
- A triplet of consecutive 0‘s or 1‘s remains unchanged.
- A triplet of consecutive array elements consisting of two 0’s and a single 1 or vice versa can be converted to more frequent element.
Examples:
Input: arr[] = {0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1}
Output: No
Explanation:
Following are the operations performed on the array:
{0, 1, 1} -> 1 modifies the array to {1, 1, 1, 0, 0, 1, 1, 1, 1}
{1, 0, 0} -> 0 modifies the array to {1, 1, 0, 1, 1, 1, 1}
{1, 0, 1} -> 1 modifies the array to {1, 1, 1, 1, 1}
Since, all the remaining elements are 1, they remain unchanged.
Therefore, the array cannot be reduced to a single element.Input: arr[] = {1, 0, 0, 0, 1, 1, 1}
Output: Yes
Explanation:
Following are the operations performed on the array:
{1, 0, 0} -> 0 {0, 0, 1, 1, 1}
{0, 0, 1} -> 0 {0, 1, 1}
{0, 1, 1} -> 1 {1}
Approach:
Follow the steps below to solve the problem:
- Count the frequency of 0‘s and 1‘s.
- Calculate the absolute difference their respective counts.
- If the difference is 1, only then the array can be reduced to 1. Therefore, print Yes.
- Otherwise, print No.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to check if it is possible to // reduce the array to a single element void solve( int arr[], int n) { // Stores frequency of 0's int countzeroes = 0; // Stores frequency of 1's int countones = 0; for ( int i = 0; i < n; i++) { if (arr[i] == 0) countzeroes++; else countones++; } // Condition for array to be reduced if ( abs (countzeroes - countones) == 1) cout << "Yes" ; // Otherwise else cout << "No" ; } // Driver Code int main() { int arr[] = { 0, 1, 0, 0, 1, 1, 1 }; int n = sizeof (arr) / sizeof (arr[0]); solve(arr, n); return 0; } |
Java
// Java program to implement // the above approach class GFG{ // Function to check if it is possible to // reduce the array to a single element static void solve( int arr[], int n) { // Stores frequency of 0's int countzeroes = 0 ; // Stores frequency of 1's int countones = 0 ; for ( int i = 0 ; i < n; i++) { if (arr[i] == 0 ) countzeroes++; else countones++; } // Condition for array to be reduced if (Math.abs(countzeroes - countones) == 1 ) System.out.print( "Yes" ); // Otherwise else System.out.print( "No" ); } // Driver Code public static void main(String[] args) { int arr[] = { 0 , 1 , 0 , 0 , 1 , 1 , 1 }; int n = arr.length; solve(arr, n); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to implement # the above approach # Function to check if it is possible to # reduce the array to a single element def solve(arr, n): # Stores frequency of 0's countzeroes = 0 ; # Stores frequency of 1's countones = 0 ; for i in range (n): if (arr[i] = = 0 ): countzeroes + = 1 ; else : countones + = 1 ; # Condition for array to be reduced if ( abs (countzeroes - countones) = = 1 ): print ( "Yes" ); # Otherwise else : print ( "No" ); # Driver Code if __name__ = = '__main__' : arr = [ 0 , 1 , 0 , 0 , 1 , 1 , 1 ]; n = len (arr); solve(arr, n); # This code is contributed by Amit Katiyar |
C#
// C# program to implement // the above approach using System; class GFG{ // Function to check if it is possible to // reduce the array to a single element static void solve( int []arr, int n) { // Stores frequency of 0's int countzeroes = 0; // Stores frequency of 1's int countones = 0; for ( int i = 0; i < n; i++) { if (arr[i] == 0) countzeroes++; else countones++; } // Condition for array to be reduced if (Math.Abs(countzeroes - countones) == 1) Console.Write( "Yes" ); // Otherwise else Console.Write( "No" ); } // Driver Code public static void Main(String[] args) { int []arr = { 0, 1, 0, 0, 1, 1, 1 }; int n = arr.Length; solve(arr, n); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to implement // the above approach // Function to check if it is possible to // reduce the array to a single element function solve(arr, n) { // Stores frequency of 0's var countzeroes = 0; // Stores frequency of 1's var countones = 0; for ( var i = 0; i < n; i++) { if (arr[i] == 0) countzeroes++; else countones++; } // Condition for array to be reduced if (Math.abs(countzeroes - countones) == 1) document.write( "Yes" ); // Otherwise else document.write( "No" ); } // Driver Code var arr = [ 0, 1, 0, 0, 1, 1, 1 ]; var n = arr.length; solve(arr, n); // This code is contributed by rutvik_56 </script> |
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)