WAP to output all the intervals (i, j) where the number of 0s and numbers of 1s are equal.You have an array of 0s and 1s. Efficiently

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.