Given a one dimensional array arr[] consisting only of 0s and 1s, write a program which returns the length of the largest subarray which has equal numbers of 0s and 1s.
For example, if arr[] = {0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1}, then your program should print 14 to STDOUT. Explanation: Subarray in Index 0 to Index 13 has an equal number of 0s and 1s. Hence the length 14.
Input Format The first line of input contains ‘t’ which is the number of test cases. “t” test cases follow. In each test case, first line contains N, which is the number of elements in array arr[]. Next line contains N space separated integers denoting elements of the array arr[].
Output Format For each of the test cases, print the length of the largest such subarray.
Here is Simple Logic.Hope it helps.
#include <iostream>
using namespace std;
int main() {
int N;
cin>>N;
int arr[N];
int i;
int count0 = 0, count1 = 0;
int maxSubset = 0;
for (i=0; i<N; i++) {
cin>>arr[i];
}
for (i=0; i<N; i++) {
if(arr[i] == 0) {
count0++;
}
else {
count1++;
}
if(count0 == count1) {
maxSubset = i+1;
}
}
cout<<maxSubset<<endl;
return 0;
}
Look at the problem in different way…lets code 0 as open parentheses ans and 1 as a closed parentheses now the problem converted to finding out the length of the longest valid parenthesis substring, which is very well known problem.
this might help : link
I think your solution fails on certain inputs…because you are only considering the subarray starts with first index…for instance 0 0 1 answer is 2 your code outputs 0
