Author |
Topic: Maximum Subarray with equal no of 1s and 0s (Read 6454 times) |
|
sateesp
Newbie
Gender: 
Posts: 35
|
 |
Maximum Subarray with equal no of 1s and 0s
« on: Mar 11th, 2010, 11:15pm » |
 Quote  Modify
|
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
|
|
 IP Logged |
|
|
|
mmgc
Newbie
Gender:
Posts: 47
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #1 on: Mar 13th, 2010, 1:26am » |
Quote Modify
|
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 )
|
|
IP Logged |
|
|
|
newCoder
Newbie
Gender:
Posts: 3
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #2 on: Mar 13th, 2010, 2:24am » |
Quote Modify
|
Please ignore formatting, its pretty well formatted in editor but somehow not here.
| hidden: |
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;
}
}
|
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
|
|
IP Logged |
|
|
|
blackJack
Junior Member
2b \/ ~2b
Gender:
Posts: 55
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #3 on: Mar 14th, 2010, 6:02am » |
Quote Modify
|
@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
|
| « Last Edit: Mar 14th, 2010, 6:03am by blackJack » |
IP Logged |
|
|
|
AB
Newbie
Posts: 20
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #4 on: Mar 15th, 2010, 1:24am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
blackJack
Junior Member
2b \/ ~2b
Gender:
Posts: 55
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #5 on: Mar 15th, 2010, 1:43am » |
Quote Modify
|
your code is goin in infinite loop for [0,0,1,0,0] at statement
Code:
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.
|
|
IP Logged |
|
|
|
sateesp
Newbie
Gender:
Posts: 35
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #6 on: Mar 15th, 2010, 2:41am » |
Quote Modify
|
@abhay.bansal, @newCoder, could you explain your logic for this. We Will first resolve or solve the problem at the algorithm level.
|
|
IP Logged |
|
|
|
AB
Newbie
Posts: 20
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #7 on: Mar 15th, 2010, 3:35am » |
Quote Modify
|
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;
} |
|
|
|
IP Logged |
|
|
|
AB
Newbie
Posts: 20
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #8 on: Mar 15th, 2010, 3:38am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
blackJack
Junior Member
2b \/ ~2b
Gender:
Posts: 55
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #9 on: Mar 15th, 2010, 4:01am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
blackJack
Junior Member
2b \/ ~2b
Gender:
Posts: 55
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #10 on: Mar 15th, 2010, 4:49am » |
Quote Modify
|
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;
}
}
|
|
|
| « Last Edit: Mar 15th, 2010, 4:52am by blackJack » |
IP Logged |
|
|
|
sateesp
Newbie
Gender:
Posts: 35
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #11 on: Mar 15th, 2010, 12:11pm » |
Quote Modify
|
@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.
|
|
IP Logged |
|
|
|
blackJack
Junior Member
2b \/ ~2b
Gender:
Posts: 55
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #12 on: Mar 15th, 2010, 10:42pm » |
Quote Modify
|
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));
}
}
|
|
|
| « Last Edit: Mar 15th, 2010, 10:42pm by blackJack » |
IP Logged |
|
|
|
AB
Newbie
Posts: 20
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #13 on: Mar 15th, 2010, 11:24pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
sateesp
Newbie
Gender:
Posts: 35
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #14 on: Mar 16th, 2010, 12:08am » |
Quote Modify
|
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)
|
|
IP Logged |
|
|
|
AB
Newbie
Posts: 20
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #15 on: Mar 16th, 2010, 1:32am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #16 on: Mar 16th, 2010, 3:20am » |
Quote Modify
|
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.
|
| « Last Edit: Mar 16th, 2010, 3:48am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
AB
Newbie
Posts: 20
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #17 on: Mar 16th, 2010, 3:31am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
spicy
Newbie
Gender: 
Posts: 8
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #18 on: Mar 16th, 2010, 3:55am » |
Quote Modify
|
@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. 
|
|
IP Logged |
|
|
|
AB
Newbie
Posts: 20
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #19 on: Mar 16th, 2010, 4:01am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #20 on: Mar 16th, 2010, 4:11am » |
Quote Modify
|
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.
|
| « Last Edit: Mar 16th, 2010, 4:25am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
AB
Newbie
Posts: 20
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #21 on: Mar 16th, 2010, 4:25am » |
Quote Modify
|
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;
|
|
IP Logged |
|
|
|
spicy
Newbie
Gender:
Posts: 8
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #22 on: Mar 16th, 2010, 5:06am » |
Quote Modify
|
@AB
I still have doubts , can you write your final code once again after all these modification.
Thx 
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #23 on: Mar 19th, 2010, 9:03am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
blackJack
Junior Member
2b \/ ~2b
Gender:
Posts: 55
|
|
Re: Maximum Subarray with equal no of 1s and 0s
« Reply #24 on: Mar 20th, 2010, 1:33am » |
Quote Modify
|
@hippo ... can you explain with a small example .. what will be the values of your variables at each character read.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print