CareerCup

Step-1: Convert all 0 to -1 (to simplify understanding)
step-2: Keep total of all elements values and put that in hashtable.
For exa:
10111000110011 => 1-1111-1-1-111-1-111
Now Keep Sum all the time.
10123210121012

Also put index of sum array in hash. i.e. insert_hash(1,0), insert_hash(0,1), insert_hash(1,2), insert_hash(2,3) and so on..

Now, Each sum can map to sum-1 to its right and each sum can map to sum+1 to its left.

For exa: 1 can map with all 0s to its right.
Any 2 will map to all 3s to its left

Any 3 will map to all 2s to its right and all 4s to its left.

Processing time O(N)
Extra space: O(N) in hash table

I think there is no linear time alg, since in the worst case, there are sum(i) = n(n+1)/2 -1 combinations

A possible solution.
1. Convert the array such that arr[i]=(number of zeros-number of ones) in original arr [0]to arr[i]...can be done in O(n)
2. Now, find all the indexes pairs (m,n), m<n such that arr[m-1] is equal to arr[n].
3. Convert back the array to original form...again can be done in O(n).

The main problem here is to do step 2 in O(n). One thing we can do is to hash the modified array with element as the key and index as the value. But, again corresponding to one element there can be different indexes in the hash. So,if we find that element again, we will have to pair up its index with all the indexes (index+1) in the hash corresponding to that element. I am not sure if its gonna be O(n).

Are you sure if it is possible in linear time?

Yeah..exactly, the 2nd step requires forming all the index pairs, which would take a complexity of O(num_pairs)

Take two Counters for 0 (ZCtr) and 1 (OCtr) set to 0.
If index [0] has 0, Initiate with ZCtr else OCtr,
For example start with 0.
Increment the counter till "1" found.
Switch the counter to OCtr.
Increment till "0" found.
Compare two counter
If Match : First Pattern found Reset both counter to 0.
If not Reset ZCtr.
Do till array ends.

Hope it works :-)

There is no linear solution as there are O(n^2) intervals from an array of length N as all 0s and 1s must be consecutive. For each interval, determine if 0s == 1s (let's calls isEqual(int i, int j)) takes O(k) where k is the size of the interval. Hence, there are O(n^3).
Observations:
1. Let’s replace 0s with -1(thank you Jack), we can see that for a given interval I(i,j):
a) if sum(I(i,j)) < 0 there are 0s > 1s
b) if sum(I(i,j)) > 0 there are 1s > 0s
c) if sum(I(i,j)) == 0 there are 0s == 1s

2. an interval I(i,j) has equal number of 0s and 1s if I(i+1,j-1):
d) sum(I(i+1,j-1)) == 0 and a[i] != a[j] or
e) sum(I(i+1,j-1)) == -2 and a[i] == a[j] == 1 or
f) sum(I(i+1,j-1)) == -2 and a[i] == a[j] == 0.

3. an interval I(i,i+1) is you-know-what if a[i] != a[i+1] --> base case

So we can reduce complexity of isEqual(int i, int j) to O(1) using dynamic programming.

1 First build an NxN matrix then fill all base cases I(i,i) diagonally.
2. do the following procedure

For (k=2;k<N;k+=2) do
For (i=0;i<=N-k) do
I(i,j) = a[i] + a[j] + I(i+1,j-1) // j = i+k-1
If I(i,j) == 0 then print interval
End
End

There is no linear solution as there are O(n^2) intervals from an array of length N 
as all 0s and 1s must be consecutive. For each interval, determine if 0s == 1s 
(let's calls isEqual(int i, int j)) takes O(k) where k is the size of the interval.
Hence, there are O(n^3).
Observations:
1. Let’s replace 0s with -1(thank you Jack), we can see that for a given interval I(i,j): 
a) if sum(I(i,j)) < 0 there are 0s > 1s 
b) if sum(I(i,j)) > 0 there are 1s > 0s
c) if sum(I(i,j)) == 0 there are 0s == 1s
2. an interval I(i,j) has equal number of 0s and 1s if I(i+1,j-1): 
d) sum(I(i+1,j-1)) == 0 and a[i] != a[j] or
e) sum(I(i+1,j-1)) == -2 and a[i] == a[j] == 1 or
f) sum(I(i+1,j-1)) ==  2 and a[i] == a[j] == 0.
3. an interval I(i,i+1) is you-know-what if a[i] != a[i+1] --> base case

So we can reduce complexity of isEqual(int i, int j) to O(1) using dynamic programming.

1 First build an NxN matrix then fill all base cases I(i,i) diagonally.
2.Do the following procedure

For (k=2;k<N;k+=2) do
	For (i=0;i<=N-k) do
		I(i,j) = a[i] + a[j] + I(i+1,j-1) // j = i+k-1
		If I(i,j) == 0 then print interval
	End
End

hhhhhh

You can count them in O(N), but not output them...

We can just keep a vector of size 2n+1 (-n to +n) which keeps the positions of original array
Where Vector position i specifies that from travelling from beginning of array to some positions difference between number of 0's and 1's will be i
now let this V(k) has position p,q,r
so one of the possible solution will (p+1,q),(q+1,r),(p+1,r)

Also add -1 at the 0th postns of vector as we are taking something like (p+1,r) kind of thing
All the finding will be O(n)
Yeah but displaying sets is just a iterative thing for me its O(n^2) If someone can suggest a better method please

There is actually a O(N) algorithm. Suppose the input is data[1...n]. We make a new array which is called count[1...n]. count[i] means the amount difference between 0s and 1s for data[1...i]. If (i,j) is a interval in which the number of 0s and 1s are the same, then count[i]=count[j]. So we just apply radix sort to sort count[1...n] and to find all the identical values in count[1...n]. Radix sort is O(N).

int[] arrs = {0,0,1,0,0,1,1,1,1,0}; //prepend a zero to the array
		int i = 0;
		HashMap<Integer,Stack<Integer>> hm = new HashMap<Integer,Stack<Integer>>();
		Stack<Integer> stk;
		stk = new Stack<Integer>();
		stk.push(0);
		hm.put(0, stk);
		
		for(i = 1; i<arrs.length ; i++)
		{//count from zero
			if(arrs[i] == 0)
			{
				arrs[i] = -1;
			}
			arrs[i] += arrs[i-1];
			if(!hm.containsKey(arrs[i]))
			{
				stk = new Stack<Integer>();
				hm.put(arrs[i], stk);
			}else
			{
				stk = hm.get(arrs[i]);
			}
			stk.push(i); // in fact, we can push the item in an increasing order
		}
		for(i = 1; i < arrs.length; i++)
		{
			stk = hm.get(arrs[i]);
			for(Integer x : stk)
			{
				if(x < i)
				{
					System.out.println( "( " + x + " , " + (i-1) + " )" );
				}
			}
			
		}

count in O(n)
while output in almost O(n^2)

O(n*(n-1)) = O(n^2) solution in C#:

static void GetIntervals()
{
int[] array = {0,0,1,0,0,1,1,1,1,0}; //prepend a zero to the array

for (int x=0; x<array.Length; x++)
if (array[x]==0) array[x]=-1;

for (int i = 0; i < array.Length - 1; i++)
{
int sum=array[i];

for (int j = i+1; j < array.Length; j++)
{
sum += array[j];
if (sum == 0)
Console.WriteLine("({0}, {1})", i, j);
}
}
}

* create a count array. Which starts with counting 1 or 0 till that point.

void printIntervals(vector<int>& in) {
        vector<int> count(in.size(),1);
        // get the count till that point
        for(int i=1;i<in.size(); ++i) {
            if (in[i] == in[i-1]) { 
                count[i] += count[i+1]; 
            }
        }
        // now go the reverse array..
        for(int i=in.size()-2; i >= 0; ++i) {
             if (in[i] == in[i+1]) {
                count[i] = count[i+1];
             }
        }
        // at this point we have span of all the 1s and all 0s..
        // Now iterate thru the count array and if count[i] == count[i-1] && in[i] != in[i-1], we have our range
        for(int i =1; i < count.size();) {
            if (count[i] == count[i-1] && in[i] != in[i-1]) {
                 cout << "Interval: " << i-count[i] << "," << i+count[i]-1 << endl;
                 i += count[i];
            } else {
                ++i;
           }
        }
  }

Complexity: 3 iterations of array.. so it is O(n).

01010101010101 -> n-1 intervals with 2 entries
01010101010101 -> n-3 intervals with 4 entries
01010101010101 -> n-5 intervals with 6 entries
...
01010101010101 -> n-1-2k intervals with 2k entries

implies that there are O(n^2) intervals with balanced 0 and 1... (Gauss sum)
implies that there is no linear solution to this problem!

keep 2 index say start and end. Initialize both to 0.
Keep a counter (number of extra ones)

for each i 1 to n
	change counter according to arr[i]
	if counter == 0
		print start,end
	else if arr[start] == arr[i] == 1 and counter > 0
		increment start;
	else if arr[start] == arr[i] == 0 and counter < 0
		increment start;

/* An efficient program to print subarray with sum as given sum */
#include<stdio.h>
 
/* Returns true if the there is a subarray of arr[] with sum equal to 'sum'
   otherwise returns false.  Also, prints the result */
int subArraySum(int arr[], int n, int sum)
{
    /* Initialize curr_sum as value of first element
       and starting point as 0 */
    int curr_sum = arr[0], start = 0, i,max=0;
 
    /* Add elements one by one to curr_sum and if the curr_sum exceeds the
       sum, then remove starting element */
    for (i = 1; i <= n; i++)
    {
        // If curr_sum exceeds the sum, then remove the starting elements
        while (curr_sum > sum && start < i-1)
        {
            curr_sum = curr_sum - arr[start];
            start++;
        }
 
        // If curr_sum becomes equal to sum, then return true
        if (curr_sum == sum)
        {
            printf ("Sum found between indexes %d and %d\n", start, i-1);
	    //if(i-start>max)
		//max=i-start;
        }
 
        // Add this element to curr_sum
        if (i < n)
          curr_sum = curr_sum + arr[i];
    }
 	return max;
}
 
// Driver program to test above function

int main()
{
    int arr[] = {-1,1,-1,-1,1,1,1,1,-1};
    int n = sizeof(arr)/sizeof(arr[0]);
    int sum = 0;
	subArraySum(arr, n, sum);
    return 0;
}

this is a modified version of code i found online,basically convert zeroes to -1 and find all subarrays whose sum is zero.Seems to work for our case and the author of the original code claims it is O(n)..

This can be done through dynamic programming effieciently.
We maintain an extra array to store the the no of intervals for i th index where
0<i<n;

Lets call this array as T

base case :
T[0] = 0

recurrence :

T[i] = T[i-1] + cnt

where cnt is calculated by the below logic
while (i>0){

1.search till the start of orginal array, from index i
2. whenever we find 0s == 1s, we increment the cnt
i--;

}

repeat this process for all i

public IList<IList<int>> FindRange(int[] nums)
{
IList<IList<int>> result = new List<IList<int>>();
int[] sum = new int[nums.Length];
sum[0] = nums[0] == 0 ? - 1:1;
for(int i = 1; i < nums.Length; i++)
sum[i] = sum[i-1] + (nums[i] == 0 ? -1 : 1);
Dictionary<int, List<int>> dic = new Dictionary<int, List<int>>();
dic.Add(sum[0], new List<int>{0});
for(int i = 1; i < nums.Length; i++)
{
if(sum[i] == 0)
result.Add(new List<int>{0, i});
if(dic.ContainsKey(sum[i]))
{
foreach(int index in dic[sum[i]])
result.Add(new List<int>{index + 1, i});
}
if(!dic.ContainsKey(sum[i]))
dic.Add(sum[i], new List<int>());
dic[sum[i]].Add(i);
}
return result;
}

One idea is to represent the bit-sequence by the number of consecutive bits they have.
e.g.
0001111000101101 can be represented as
0-3, 1-4, 0-3, 1-1, 0-1, 1-2, 0-1, 1-1 [BALANCED]

Now you can consider the wholesum bit-sequence and start trimming the left and right sides until you reach the balance. This will the longest bitsequence you will ever get from this sequence.
For e.g. in the problem above, if you consider entire bit sequence then, you have 8 zeros and 8 ones. That is balanced already.
Now, you can shed a 0 and 1 on both sides and thus you will get your next sub-sequence which is
0-2, 1-4, 0-3, 1-1, 0-1, 1-2, 0-1 [BALANCED]
This is balanced and now you have zeros on both left and right end. Shed both of them because you cannot achieve balance by shedding them individually because you have no 1s to shed.
Shed 3 zeros and you get
1-4, 0-3, 1-1, 0-1, 1-2 [UNBALANCED by 3 zeros deficit]
and it has deficit of 3 zeros and we have shed 3 ones to achieve balance.
This can be done shedding 2 ones on the right and 1 one on the left
1-3,0-3,1-1,0-1 [BALANCED]
This is balanced.
We can again shed and 0 and 1 on both sides to get balance
1-2,0-3,1-1 [BALANCED]
Now we have 1st on both ends. We need to shed them achieve balance
This will lead to
0-3 [UNBALANCED with deficit of 1]
Applying same balance, we get a null set and thus there are no further bit-sequences.

This is way of reducing 1 full sequence to some sub-sequences within it.
But is this the maximum number of sub-sequence?

I am bit skeptical. We can adapt this algorithm further to make sure we shed only from 1 side and not from both sides. That will find all sub-sequences that start from bit position 0.
I am curious to know if this algorithm can be adapted further to run efficiently.

public static void printAllIntervals(int[] arr){
		int[][] memo = new int[arr.length][arr.length];
		change0(arr);
		for(int i = 0; i < arr.length; i++){
			for(int j = i+1; j < arr.length; j++){
				if(j == i + 1){
					memo[i][j] = arr[i] + arr[j];
				}else{
					memo[i][j] = arr[j] + memo[i][j - 1];
				}
				if(memo[i][j] == 0)
					System.out.println("(" + i + ", " + j + ")");
			}
		}
	}
	static void change0(int[] arr){
		for(int i = 0; i < arr.length; i++){
			if(arr[i] == 0)
				arr[i] = -1;
		}
	}

They are hard coded values... but I ran this in Visual C++ and it is correct, but like everyone else it still runs at worst O(n^2) I don't get how you can can get all possible sets in just one pass, without looping through the previous values to check for new sets

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;



int main(){

	int start[10]= {-1};
	int end[10]= {-1};
	int test[10]={0,1,1,0,0,0,1,0,1,0};
	int runningTotals[10] = {0};
	int x = 0;
	int var = 0;
	int n = 0;
	int idx = 0;

	for(int i = 0; i < (sizeof test/sizeof(int)); i++){
	
		if(test[i] > 0 ){ var = 1; }
		else{ var = -1;}

		cout << "before second for \n";
	
		for(n = i;  n >= 0; n--){
			runningTotals[i-n] += var;
			cout << i-n << " : "<< runningTotals[i-n] << endl;

			if( n > 0 && runningTotals[i-n] == 0){
				start[x] = i-n;
				end[x] = i;
				x++;
			}
		}
	}

	int k = 0;
	while(k < (sizeof start/sizeof(int))){
	
		if(start[k] != -1 && end[k] != -1){
			cout << "( " << start[k] << ", " << end[k] << " )\n";
		}
		k++;
	}

	return 0;
}