Given a binary array, the task is to find the size of the largest sub_sequence which having equal number of zeros and one.
Examples :
Input : arr[] = { 1, 0, 0, 1, 0, 0, 0, 1 }
Output: 6Input : arr[] = { 0, 0, 1, 1, 1, 1, 1, 0, 0 }
Output : 8
simple solution is that we generate all possible sub_sequence and find which sub_sequence have equal number of zeros & one ( it’s size should be maximum).
Below is the implementation of above idea
C++
#include <bits/stdc++.h>using namespace std;int generateSubsequences(int arr[], int n){ // store the maximum length // sub_sequence having equal // number of zeros and ones int result = 0; // Number of subsequences is (2**n -1) unsigned int opsize = pow(2, n); // Run from counter 000..1 to 111..1 for (int counter = 1; counter < opsize; counter++) { // store count of zeros and one int countzero = 0; int countone = 0, current_size = 0; for (int j = 0; j < n; j++) { // Check if jth bit in the // counter is set. If set // then print jth element // from arr[] if (counter & (1 << j)) { if (arr[j]) countone++; else countzero++; current_size++; } } // update maximum size if (countzero == countone) result = max(current_size, result); } return result;}// Driver Codeint main(){ int arr[] = { 1, 0, 0, 1, 0, 0, 0, 1 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "largest Subsequences having " "equal number of 0 & 1 is " << generateSubsequences(arr, n); return 0;} |
Java
// Java program for Longest subsequence// having equal numbers of 0 and 1import java.io.*;class GFG { static int generateSubsequences(int arr[], int n){ // store the maximum length // sub_sequence having equal // number of zeros and ones int result = 0; // Number of subsequences // is (2**n -1) long opsize = (long) Math.pow(2, n); // Run from counter // 000..1 to 111..1 for (int counter = 1; counter < opsize; counter++) { // store count of zeros and one int countzero = 0; int countone = 0, current_size = 0; for (int j = 0; j < n; j++) { // Check if jth bit in the // counter is set. If set // then print jth element // from arr[] if ((counter & (1 << j))>0) { if (arr[j]>0) countone++; else countzero++; current_size++; } } // update maximum size if (countzero == countone) result = Math.max(current_size, result); } return result;} // Driver Code public static void main (String[] args) { int arr[] = { 1, 0, 0, 1, 0, 0, 0, 1 }; int n = arr.length; System.out.println( "largest Subsequences having "+ "equal number of 0 & 1 is "+ generateSubsequences(arr, n)); }}// This code is contributed by anuj_67. |
Python3
# Python code to find the # length of longest subsequence# having equal no of 1 and 0def generateSubsequences(a, n): result = 0 # Number of subsequences # is (2**n -1) opsize = 2**n # Run from counter # 000..1 to 111..1 for counter in range(opsize): # store count of zeros and one countzero, countone = 0, 0 current_size = 0 for j in range(n): # Check if jth bit in the # counter is set. If set then # print jth element from arr[] if counter & (1 << j): if arr[j] == True: countone += 1 else: countzero += 1 current_size += 1 # update maximum size if countzero == countone: result = max(current_size, result) return result # Driver codearr = [ 1, 0, 0, 1, 0, 0, 0, 1 ]n = len(arr)print("largest Subsequences having" + " equal number of 0 & 1 is ", generateSubsequences(arr, n))# This code is contributed# by "Abhishek Sharma 44" |
C#
// C# program for Longest subsequence// having equal numbers of 0 and 1using System;class GFG { static int generateSubsequences(int []arr, int n){ // store the maximum length // sub_sequence having equal // number of zeros and ones int result = 0; // Number of subsequences // is (2**n -1) uint opsize = (uint) Math.Pow(2, n); // Run from counter // 000..1 to 111..1 for (int counter = 1; counter < opsize; counter++) { // store count of zeros and one int countzero = 0; int countone = 0, current_size = 0; for (int j = 0; j < n; j++) { // Check if jth bit in the // counter is set. If set // then print jth element // from arr[] if ((counter & (1 << j))>0) { if (arr[j]>0) countone++; else countzero++; current_size++; } } // update maximum size if (countzero == countone) result = Math.Max(current_size, result); } return result;} // Driver Code public static void Main () { int []arr = { 1, 0, 0, 1, 0, 0, 0, 1 }; int n = arr.Length; Console.WriteLine("largest Subsequences having "+ "equal number of 0 & 1 is "+ generateSubsequences(arr, n)); }}// This code is contributed by anuj_67. |
PHP
<?php// PHP code to find the length // of longest subsequence have// equal no of 1 and 0function generateSubsequences($arr, $n){ // store the maximum length // sub_sequence having equal // number of zeros and ones $result = 0; // Number of subsequences // is (2**n -1) $opsize = pow(2, $n); // Run from counter 000..1 // to 111..1 for ($counter = 1; $counter < $opsize; $counter++) { // store count of zeros and one $countzero = 0; $countone = 0; $current_size = 0; for ($j = 0; $j < $n; $j++) { // Check if jth bit in // the counter is set // If set then print jth // element from arr[] if ($counter & (1 << $j)) { if ($arr[$j]) $countone++; else $countzero++; $current_size++; } } // update maximum size if ($countzero == $countone) $result = max($current_size, $result); } return $result;}// Driver Code$arr = array(1, 0, 0, 1, 0, 0, 0, 1);$n = count($arr);echo "largest Subsequences having " , "equal number of 0 & 1 is " , generateSubsequences($arr, $n); // This code is contributed by anuj_67.?> |
Javascript
<script>// JavaScript program for Longest subsequence// having equal numbers of 0 and 1function generateSubsequences(arr, n){ // store the maximum length // sub_sequence having equal // number of zeros and ones var result = 0; // Number of subsequences is (2**n -1) var opsize = Math.pow(2, n); // Run from counter 000..1 to 111..1 for (var counter = 1; counter < opsize; counter++) { // store count of zeros and one var countzero = 0; var countone = 0, current_size = 0; for (var j = 0; j < n; j++) { // Check if jth bit in the // counter is set. If set // then print jth element // from arr[] if (counter & (1 << j)) { if (arr[j]) countone++; else countzero++; current_size++; } } // update maximum size if (countzero == countone) result = Math.max(current_size, result); } return result;}// Driver Codevar arr = [ 1, 0, 0, 1, 0, 0, 0, 1 ];var n = arr.length;document.write( "largest Subsequences having "+ "equal number of 0 & 1 is " + generateSubsequences(arr, n));</script> |
Output:
largest Subsequences having equal number of 0 & 1 is 6
Time Complexity: (n*2^n)
Auxiliary Space: O(1)
Efficient solution is to count zeros & ones in a binary array and last return minimum between count of zeros & ones by multiplying it with 2.
arr[] = { 1, 0, 0, 1, 0, 0, 0, 1 }
output : 6
here largest sub_sequencer :
{ 1 0 0 1 0 1} or {1 0 1 0 0 1 }
If we observe carefully then we notice that
we just have to find minimum counts between
zeros & ones and multiplying it with 2
( because we always get even length sub_sequence)
Below is the implementation of the above idea:
C++
// Efficient CPP program to find // length of the longest subsequence // with equal number of 0s and 1s.#include <bits/stdc++.h>using namespace std;int largestSubsequences(int arr[], int n){ // store count of zeros and one int countzero = 0, countone = 0; // traverse binary array and count // zeros and ones for (int i = 0; i < n; i++) if (arr[i]) countone++; else countzero++; return min(countone, countzero) * 2;}// Driver programint main(){ int arr[] = { 1, 0, 0, 1, 0, 0, 0, 1 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "largest Subsequences having " << "equal number of 0 & 1 is " << largestSubsequences(arr, n); return 0;} |
Java
// Efficient Java program to find // length of the longest subsequence// with equal number of 0s and 1s.import java.io.*;import java.math.*;class GFG { static int largestSubsequences(int arr[], int n) { // store count of zeros and one int countzero = 0, countone = 0; // traverse binary array and count // zeros and ones for (int i = 0; i < n; i++) if (arr[i] == 1) countone++; else countzero++; return Math.min(countone, countzero) * 2; } // Driver Code public static void main(String args[]) { int arr[] = { 1, 0, 0, 1, 0, 0, 0, 1 }; int n = arr.length; System.out.println("largest Subsequences having " + "equal number of 0 & 1 is " + largestSubsequences(arr, n)); }}// This code is contributed by Nikita Tiwari |
Python3
# Efficient Python code to find # length of the longest subsequence # with equal number of 0s and 1s.def largestSubsequence(arr,n): # store count of zeros and one countzero = 0 countone = 0 # traverse binary array and count # zeros and ones for i in range(n): if arr[i]: countone += 1 else: countzero += 1 return min(countone, countzero) * 2 # Driver Codearr = [ 1, 0, 0, 1, 0, 0, 0, 1 ]n = len(arr)print("largest Subsequences having" + " equal number of 0 & 1 is ", largestSubsequence(arr, n)) # This code is contributed# by "Abhishek Sharma 44" |
C#
// Efficient C# program to find // length of the longest subsequence // with equal number of 0s and 1s.using System;class GFG{ static int largestSubsequences(int[] arr, int n) { // store count of zeros and one int countzero = 0, countone = 0; // traverse binary array and // count zeros and ones for (int i = 0; i < n; i++) if (arr[i] != 0) countone++; else countzero++; return Math.Min(countone, countzero) * 2; } // Driver Code static void Main() { int[] arr = { 1, 0, 0, 1, 0, 0, 0, 1 }; int n = 8 ; Console.Write("largest Subsequences having" + " equal number of 0 & 1 is " + largestSubsequences(arr, n)); }} // This code is contributed by Anuj_67 |
PHP
<?php// Efficient PHP program to find // length of the longest subsequence // with equal number of 0s and 1s.function largestSubsequences( $arr, $n){ // store count of zeros and one $countzero = 0; $countone = 0; // traverse binary array and // count zeros and ones for ( $i = 0; $i < $n; $i++) if ($arr[$i]) $countone++; else $countzero++; return min($countone, $countzero) * 2;}// Driver Code$arr = array(1, 0, 0, 1, 0, 0, 0, 1);$n = count($arr);echo "largest Subsequences having " , "equal number of 0 & 1 is " , largestSubsequences($arr, $n);// This code is contributed by Anuj_67.?> |
Javascript
<script>// Efficient Javascript program to find // length of the longest subsequence // with equal number of 0s and 1s.function largestSubsequences(arr, n){ // store count of zeros and one var countzero = 0, countone = 0; // traverse binary array and count // zeros and ones for (var i = 0; i < n; i++) if (arr[i]) countone++; else countzero++; return Math.min(countone, countzero) * 2;}// Driver programvar arr = [1, 0, 0, 1, 0, 0, 0, 1 ];var n = arr.length;document.write( "largest Subsequences having " + "equal number of 0 & 1 is " + largestSubsequences(arr, n));</script> |
Output
largest Subsequences having equal number of 0 & 1 is 6
Time Complexity : O(n)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
