Example
pos = 0 1 2 3 4 5 6 7 8
arr = 0 1 0 0 1 1 1 1 0
One interval is (0, 1) because there the number of 0 and 1 are
equal.There are many other intervals, find all of them in linear time.
A naive Algorithm will take O(N^3) of time find all such interval
if wont pre-process till auxiliary array x (where each x[i] will0
contains the cumulative sum from o to ith index)because in this
case we need to find all i,j such that they represents equal number
of 0s & 1s so it will take O(N^3) Time.
But This Algo Will fail for array like 1 0 1 0 1 0 1 0
you can run here above Algo will print only few intervals
but as i have counted contains 16 such intervals which are
of equal numbers of 0s & 1s.
2nd Algorithm O(N^2) Efficient
Approach
In This question we need to find all the intervals and in worst case
no of intervals can grow as large as O(n^2) so hashing will not work
we need to form as adjacency list type of thing :(
here what i m trying to do is after calculating the array x if any x[i]
is zero means that that sum of elements from 0 to i is zero hence it
contains equal no of zeros and ones. so for every x[i] = 0 [0,i] is
a solution, ans also for every x[i] and x[j] if(x[i] == x[j]) implies
that sum does not changes from x[i] to x[j] hence equal no of 0's and
1's [i+1,j].
now what i think is finding all the intervals is going to be O(n^2)
1.Pre-processing Step
a.Replace all zeros with -1
b.calculate cumulative array X such each x[i] represents the sum from 0
to ith index in array A
2.Check for every ith index in X array if
a. x[i]==0 then we have found the interval in 0 to i
b. else check for every i if x[i]==x[j] then print the interval from i+1toj
#include <iostream> using namespace std; void isASolution(int i, int j){ cout << "Interval [" << i << "," << j <<"] contains equal no of 0's and 1's\n"; } void Solve(int a[], int size){ // replacing 0 with -1 for(int i = 0; i < size; i++){ a[i] = 2*a[i] - 1; } int x[100]; //x[i] contains sum of values in a from 0 to ith position x[0] = a[0]; cout << x[0] << " "; for(int i = 1; i < size; i++){ x[i] = x[i-1] + a[i]; cout << x[i] <<" "; } cout << endl; for(int i = 0; i < size; i++){ if(x[i] == 0){ isASolution(0,i); } for(int j = i+1; j < size; j++){ if(x[i] == x[j]){ isASolution(i+1,j); } } } } int main(){ int a[9] = {1,0,1,0,1,0,1,0};//{0, 1, 0, 1, 1, 1, 1, 0, 0}; int n = sizeof(a)/sizeof(a[0]); Solve(a,n); }
Time Complexity O(N^2)
Space Complexity O(1)
Run Here http://ideone.com/dF52e
Feel Free To Comment, Suggest new Algorithm & Optimize The Solution
Variation:Find the maximum length subarray which maximize the no of 0s and 1s.