Edit Question - KnowledgeHub

Title Body

given an array of 0s and 1s, find maximum subarray such that number of zeros and 1s are equal. This needs to be done in O(n) time and O(1) space. I have an algo which does it in O(n) time and O(n) space. It uses a prefix sum array and exploits the fact that if the number of 0s and 1s are same then sumOfSubarray = lengthOfSubarray/2 #include<iostream> #define M 15 using namespace std; void getSum(int arr[],int prefixsum[],int size) { int i; prefixsum[0]=arr[0]=0; prefixsum[1]=arr[1]; for (i=2;i<=size;i++) { prefixsum[i]=prefixsum[i-1]+arr[i]; } } void find(int a[],int &start,int &end) { while(start < end) { int mid = (start +end )/2; if((end-start+1) == 2 * (a[end] - a[start-1])) break; if((end-start+1) > 2 * (a[end] - a[start-1])) { if(a[start]==0 && a[end]==1) start++; else end--; } else { if(a[start]==1 && a[end]==0) start++; else end--; } } } int main() { int size,arr[M],ps[M],start=1,end,width; ; cin>>size; arr[0]=0; end=size; for (int i=1;i<=size;i++) cin>>arr[i]; getSum(arr,ps,size); find(ps,start,end); if(start!=end) cout<<(start-1)<<" "<<(end-1)<<endl; else cout<<"No soln\n"; return 0; }

Tags (comma-separated) Cancel