wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Maximum Subarray with equal no of 1s and 0s
        
(Message started by: sateesp on Mar 11^th, 2010, 11:15pm)

Title: Maximum Subarray with equal no of 1s and 0s
Post by sateesp on Mar 11^th, 2010, 11:15pm

There is an array of size 'n' containing 0s and 1s. Find in O(n) and constant space
the maximum sub sequence which has equal number of 1s and 0s

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by mmgc on Mar 13^th, 2010, 1:26am

Assuming sub-sequence can be non-continuous :Traverse the array, summing all elements - calculate the number of 1's and 0's --traverse again and print the subsequence ( minium number of 1's or 0's )

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by newCoder on Mar 13^th, 2010, 2:24am

Please ignore formatting, its pretty well formatted in editor but somehow not here.

[hideb]
int findMaxSumSubSequence(int arr*, int size, int &start, int &end, int &maxSum)
{
int i, j , runningSum, numOfZero,numOfOne ;
runningSum = numOfZero = numOfOne = i = j = 0;
start = end = 0;
int totalNumOfZero = ComputeCount(arr,0); // find total number of zero's
int totalNumOfOnes = ComputeCount(arr,1); // find total number of One's
int delta = totalNumOfZero - totalNumOfOnes;
bool deltaCovered = false;

while( j < size ){

runningSum +=arr[j];
arr[j] ? numOfOne++ : numOfZero++ ;

if( (numOfOne == numOfZero) && runningSum > maxSum){
start = i;
end=j;
maxSum = runningSum;
}

if( (numOfZero-numOfOne == delta) && !deltaCovered){
i = j+1;
runningSum = 0;
deltaCovered = true;
numOfZero=numOfOne = 0;
}
++j;
}
}
[/hideb]

Using above O/P for these e.g. are in bold :-

1110011010101010110001000100
0->15
1->13
D->2

0011100110101010101100010001
0->15
1->13
id->2
0001111111000011111111100000011100
1->19
0->15
Del = -4

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by blackJack on Mar 14^th, 2010, 6:02am

@newCoder, your code do not seem to work for 00100 as sequence should be 00100 or 00100 but it gives i and j as 5 and maxSum as 0.

I guess you missed the part when substring can be less than delta. When it is equal to delta than we are sure the rest of the array has equal 0's and 1's and we can print the rest of the array

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by abhay.bansal on Mar 15^th, 2010, 1:24am

Code:

int func(int[] x)
{
int sum = 0;
for (int i = 0; i < x.length; i++)
{
sum += x[i];
}
int start = 0;
int end = x.length - 1;
int dif = 0;
do
{
dif = (end - start);
int temp1 = start;
int temp2 = end;
int sum1 = 0;
int sum2 = 0;
if (dif > (2 * sum))
{
while (true)
{
sum1 += x[temp1];
sum2 += x[temp2];
if (x[temp1] == 0)
{
start = ++temp1;
sum -= sum1;
break;
}
if (x[temp2] == 0)
{
end = --temp2;
sum -= sum2;
break;
}
}
}
else
{
while (true)
{
sum1 += x[temp1];
sum2 += x[temp2];
if (x[temp1] == 1)
{
start = ++temp1;
sum -= sum1;
break;
}
if (x[temp2] == 1)
{
end = --temp2;
sum -= sum2;
break;
}
}
}
} while ((dif != (2 * sum)));
return dif;
}

Here I have calculated the sum in one traversal. Now we have to find of j - i such that j > i and are indexes of the array. Also ( j - i ) = 2 * sum.

Check the condition and move the iterators from the back as well as front. It seems fine to me. Await a response.

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by blackJack on Mar 15^th, 2010, 1:43am

your code is goin in infinite loop for [0,0,1,0,0] at statement

Code:

while (true)

and i do not get why 2*sum is needed. Can you work out an example with your code. That will help in understanding your code.

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by sateesp on Mar 15^th, 2010, 2:41am

@abhay.bansal, @newCoder, could you explain your logic for this. We Will first resolve or solve the problem at the algorithm level.

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by abhay.bansal on Mar 15^th, 2010, 3:35am

Hi there is a slight change with the numbers. Please refer to the snippet below

Code:

int func(int[] x)
{
int sum = 0;
for (int i = 0; i < x.length; i++)
{
sum += x[i];
}
int start = 0;
int end = x.length - 1;
int dif = (end - start + 1);
do
{
int temp1 = start;
int temp2 = end;
int sum1 = 0;
int sum2 = 0;
if (dif > (2 * sum))
{
while (true)
{
sum1 += x[temp1];
sum2 += x[temp2];
if (x[temp1] == 0)
{
start = ++temp1;
sum -= sum1;
break;
}
if (x[temp2] == 0)
{
end = --temp2;
sum -= sum2;
break;
}
}
}
else
{
while (true)
{
sum1 += x[temp1];
sum2 += x[temp2];
if (x[temp1] == 1)
{
start = ++temp1;
sum -= sum1;
break;
}
if (x[temp2] == 1)
{
end = --temp2;
sum -= sum2;
break;
}
}
}
dif = (end - start + 1);
} while ((dif != (2 * sum)));
return dif;
}

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by abhay.bansal on Mar 15^th, 2010, 3:38am

I have calculated the sum in one traversal. and then i move the start and end to suffice to the condition (j-i) = 2*sum.
sum is the number of ones. For the ones and 0s to be equal the difference of indexes should be equal to twice the number of ones.

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by blackJack on Mar 15^th, 2010, 4:01am

Good approach, but still fails for [1,0,0,0,1] (goes in loop)... condition is not checked when diff is greater than 2*sum and start and end are both pointed to 1's.

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by blackJack on Mar 15^th, 2010, 4:49am

made changes to AB's code and it works. Also simplified the code a bit.

Code:

public class zeroOne {

public static void main(String[] args){
zeroOne obj = new zeroOne();
int x[] = {1,0,0,0,1};
obj.func(x);
}
int func(int[] x)
{
int sum = 0;
for (int i = 0; i < x.length; i++)
{
sum += x[i];
}
int start = 0;
int end = x.length - 1;

while(start < end){
int dif = (end - start + 1);
if(dif == 2*sum){
System.out.println("start = " + start + " end = " + end + " diff = " + dif);
return dif;
}
else if(dif > 2*sum){
if(x[start] == 0){ //first priority to move frwrd start if 0
start++;
}else if(x[end] == 0){ //second priority to decrement end if 0
end--;
}else if(x[start] == 1){ //last to move forward start if 1
start++;sum--;
}
}
else{
if(x[start] == 1){
start++;sum--;
}else if(x[end] == 1){
end--;sum--;
}else if(x[start] == 0){
start++;
}
}
}
System.out.println("no such sequence");
return 0;
}
}

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by sateesp on Mar 15^th, 2010, 12:11pm

@blackJack, your program is not working for following input.

11101010111111010

maximum sub array start from 2nd location(0-based ordering of elements) and of size 6 elements.

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by blackJack on Mar 15^th, 2010, 10:42pm

thanks for poitning that out. I guess we can not use greedy approach then for the solution. We have to recursively find the max out of incrementing start OR decrementing end and go with the max.

I have changed the code for recursion. Hope now it works ::)

Code:

class Info{
int start;
int end;
int dif;

public Info(int start,int end){
this.start = start;
this.end = end;
}
}

public class zeroOne {
public static void main(String[] args){
Info tempInfo;
zeroOne obj = new zeroOne();
int x[] = {1,1,1,0,1,0,1,0,1,1,1,1,1,1,0,1,0};
tempInfo = obj.func(x,0,x.length-1);
if(tempInfo.dif == 0)
System.out.println("no such sequence");
else
System.out.println("start = " + tempInfo.start + " end= " + tempInfo.end + " dif = "+tempInfo.dif);
}
Info max(Info f1, Info f2){
if(f1.dif > f2.dif)
return f1;
else
return f2;
}

Info func(int[] x, int start, int end)
{
Info info = new Info(start,end);
if(start >= end){
info.dif = 0;
return info;
}
if(start == (end-1)){
if(((x[start])^x[end]) == 1) // if 1,0 or 0,1 then return 2
info.dif = 2;
else info.dif = 0; // if 1,1 or 0,0 return 0
return info;
}
int sum = 0;
for (int i = start; i <= end; i++)
sum += x[i];

int dif = (end - start + 1);
if(dif == 2*sum){
info.dif = dif;
return info;
}
else return max(func(x,start+1,end),func(x,start,end-1));
}
}

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by AB on Mar 15^th, 2010, 11:24pm

Code:

int recur(boolean flag, int[] a, int start, int end, int sum)
{
if (2 * sum > end - start)
{
if (flag)
{
for (int i = start; i < end; i++)
if (a[i] == 1)
{
sum--;
start = i;
}
}
else
for (int i = end; i > start; i--)
if (a[i] == 1)
{
sum--;
end = i;
}
}
else
{
if (flag)
{
for (int i = start; i < end; i++)
if (a[i] == 0)
start = i;
}
else
for (int i = end; i > start; i--)
if (a[i] == 0)
end = i;
}
if (2 * sum == (end - start))
return end - start;

int left = recur(true, a, start, end, sum);
int right = recur(false, a, start, end, sum);

if (left > right)
return left;
else
return right;
}

Cant we use recursion on the same approach. Correct me if I am wrong.

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by sateesp on Mar 16^th, 2010, 12:08am

If you use the recursion, then the complexity of algorithms goes to O(n2).

Below is my solution without recession.

Code:

int func(int x[],int n)
{
int sum = 0;
for (int i = 0; i <n; i++)
{
sum += x[i];
}
int start = 0;
int end = 0;
int maxPossibleSolution = Min(n-sum,sum);

if ( maxPossibleSolution == 0)
{
return -1;
}
int temp = 0;
int maxSubArrySum = -1;
for(int i=0;i<n;i++)
{
temp=0;
for(int j=i;j<Min(2*maxPossibleSolution,n);j++)
{
temp += x[j];

if(2*temp == j-start+1)
{
if( temp > maxSubArrySum)
{
maxSubArrySum = temp;
start = i;
end = j;
}
}
}
}
cout<<"start = " << start << " end = " << end << " diff = " << maxSubArrySum;

Can we do better than O(n2)???

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by AB on Mar 16^th, 2010, 1:32am

I don't know if this will work out.

Let say we have an array
11101010111111010
Form another array storing the sum from the the beg in as value. This can be done in O(n) time with O(n) space.
1 2 3 3 4 4 5 5 6 7 8 9 10 11 11 12 12

Code:

int find(Array a,int start,int end)
{
int mid = ( start+end )/2;
if((end-start) == 2 * (a[start] - a[end]))
return end-start;
if((a[mid]-a[start]) > (a[end]-a[mid])
return find(a,start+1,end);
else
return find(a,start,end-1);
}

This can be done in order n. Suggestions awaited.

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by towr on Mar 16^th, 2010, 3:20am

Quote:
return find(a,start+1,end);
else
return find(a,start,end-1);

Shouldn't that be

return find(a,mid+1,end);
else
return find(a,start,mid-1);

?

Not that I quite see how either accomplishes the goal; ~~but the former wouldn't give an O(n) algorithm.~~

Also, if I might suggest, instead of making an array of the plain sum, instead add 1 for each 1 and subtract 1 each 0. I know it's equivalent, but it's simpler to explain you're looking for the furthest indices apart with the same value.
Not that we have O(n) extra space to build such an array in the first place, but still.

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by AB on Mar 16^th, 2010, 3:31am

Code:

int find(Array a,int start,int end)
{
for(;start < end;)
{
int mid = (start +end )/2;
if((end-start) == 2 * (a[start] - a[end]))
break;
if((a[mid]-a[start]) > (a[end]-a[mid])
start++;
else
end--;
}
return end - start;
}

It is an order n solution and it was end instead of mid. Hope this does fine.

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by spicy on Mar 16^th, 2010, 3:55am

@AB

Will it work for following exp

1,1,1,0,0,0,1,1,0,0,0,0,0,0,0,0

I am guessing on the first step itself
if((a[mid]-a[start]) > (a[end]-a[mid])
start++;

it will miss the window.
Please correct me if i am wrong. ::)

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by AB on Mar 16^th, 2010, 4:01am

1110001100000000
The sum array will be

1 2 3 3 3 3 4 5 5 5 5 5 5 5 5 5

a[mid] - a[start] = 4 and a[end] - a[start] = 0

it will go with start++.

it will keep on increment start till it the condition is satisfied.

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by towr on Mar 16^th, 2010, 4:11am

Try 1 1 1 0 0
That gives the array 1 2 3 3 3
So when we get to
if((end-start) == 2 * (a[end] - a[start]))
We have start=0, end=4, so we get 4-0 == 2*(3-1) and break. Which is the wrong thing to do.
(Well, actually you do return the right value of 4-0 at the end, but then you have a problem with 1,1,0,0 instead. So I'm assuming the return value should have 1 added to it.)

And for 0,0,1
if we get to
if((a[mid]-a[start]) > (a[end]-a[mid])
It gives (0-0) > (1-0), and we decrement end. Which isn't the right thing to do under the circumstances.

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by AB on Mar 16^th, 2010, 4:25am

Code:

if ((end - start + 1) == 2 * (a[end] - a[start] + 1))
break;

I guess I missed on this. and the value returned will be end - start +1;

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by spicy on Mar 16^th, 2010, 5:06am

@AB
I still have doubts , can you write your final code once again after all these modification.

Thx :o

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by Hippo on Mar 19^th, 2010, 9:03am

Remember position in the string "pos", maintain "maxdif" and guarantees of the difference "minpos", "maxpos".
Start with "empty turing tape but with infinit alphabet".

Whenever standing on blank (noninitialised place),
write (pos,pos) to the tape.
Whenever place was already initialised, update just the second coordinate. Compare their diference with maxdif and update maxdif,and guarantees minpos, maxpos if required.

Main loop:
Increment pos and if there is 1 on given pos, go right on tape. In case of 0 go left. When pos reaches end of the string, minpos, maxpos contains the result.

Even if you don't have Turing tape with infinite alphabet, you can simulate it easily.

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by blackJack on Mar 20^th, 2010, 1:33am

@hippo ... can you explain with a small example .. what will be the values of your variables at each character read.

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by KWillets on Mar 23^rd, 2010, 6:06pm

It's fairly easy to keep a running sum of +1 and -1 for 0,1 respectively, and look for the widest pair of equal values. Sums are bounded by -n, n, so space and time are O(n).

Pseudo code:
[hideb]
int sum[n];
int firstOcc[ -n, n ] (initialize to -1's);
int running = 0;

int maxwidth = 0;
int maxval = 0;

for( i=0; i < n; i++ ) {
running += (a[i] == 0) ? -1 : 1 ;
sum[i] = running;
if( firstOcc[running] == -1 )
firstOcc[running] = i;
else if( i - firstOcc[running] > maxwidth ) {
maxwidth = i - firstOcc[running];
maxval = i; // location of pair
}
}

print firstOcc[ sum[maxval], maxval;
[/hideb]

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by towr on Mar 24^th, 2010, 2:56am

Such a shame we only have constant extra space to work with.

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by KWillets on Mar 24^th, 2010, 11:07pm

Ah yes.

If the original array can be overwritten with int's, I believe we can overwrite each a[i] with the first index j where sum[j] == i. If the sums are always positive this works; it may be possible to adjust the range for negative values as well (the total range can't be more than n).

While we're iterating we just keep looking up a[sum[j] and either setting it to j or checking j-a[sum[j] for maximality.

I also have a scheme for in-place backpointers (to equal values of sum) that might work.

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by byte on Apr 3^rd, 2010, 4:28pm

This is my first post. I apologize if the code doesn't appear formatted as it looks OK with white spaces in my code editor but I am finding it a bit difficult to post formatted code here.

[hideb]
Code:

int MaxSubArrayWithEqual0and1(int arr[], int arrLen, int &start, int &end)
{
int len = arrLen; // Len of array

int i = 0;

int SumOfArray = 0; // Total sum of the array
int TotalOnes = 0;
int TotalZeroes = 0;

// Calculate sum of array, total number of 1s and 0s
for (i = 0; i < len; i++)
{
SumOfArray += arr[i];

if ( arr[i] == 0 )
{
TotalZeroes ++;
}
}

TotalOnes = len - TotalZeroes;

int extras = 0;

if(TotalZeroes == arrLen || TotalOnes == arrLen)
{
return FALSE;
}

if(TotalZeroes > TotalOnes) // Zeroes are more
{
extras = TotalZeroes - TotalOnes;
}
else if(TotalZeroes < TotalOnes) // Ones are more
{
extras = TotalOnes - TotalZeroes;
}
else
{
start = 0; end = arrLen-1;
return TRUE;
}

start = end = 0;

if(TotalZeroes > TotalOnes) // Zeroes are more
{
for ( i = 0; i < len ; i++)
{
if(arr[i] == 0)
{
start ++;
TotalZeroes--;
}
else if (arr[i] == 1)
{
start --;
TotalOnes --;
}

if( (0 == TotalOnes) && (extras >= TotalZeroes) )
{
end = i;
break;
}
}
}
else
{
for ( i = 0; i < len ; i++)
{
if(arr[i] == 0)
{
start --;
TotalZeroes--;
}
else if (arr[i] == 1)
{
start ++;
TotalOnes --;
}

if( (0 == TotalZeroes) && (extras >= TotalOnes) )
{
end = i;
break;
}
}
}
return TRUE;
}

int _tmain(int argc, _TCHAR* argv[])
{
// int arr[] = {0, 0, 1, 1, 1, 0, 0, 0, 0};
// int arr[] = {0, 0, 0, 0, 1, 1, 1, 0, 0};
// int arr[] = {0, 0, 0, 0, 1, 1, 0, 1, 0, 0};
int arr[] = {1, 1, 0, 0, 0, 1, 1, 1, 1};
//int arr[] = {1, 1, 1, 1, 0, 0, 0, 1, 1};

int arrLen = sizeof(arr)/sizeof(arr[0]);
int start = 0;
int end = 0;

MaxSubArrayWithEqual0and1(arr, arrLen, start, end);

return 0;
}

[/hideb]

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by kirru on Apr 8^th, 2010, 5:49am

so finally what is the summary about this discussion??

Title: Re: Maximum Subarray with equal no of 1s and 0s
Post by sateesp on Apr 8^th, 2010, 9:48am

Till now we have 0(N) solution with O(N) space. Still we are trying to find a 0(N) solution with constant space.