this can be done in O(n) time and O(n) space:
let count = the number of 1s seen so far - the number of 0s seen so far
so for each element if it is 1 then count++ and if it is 0 count-- (count is
0 at first )
make a map m[] such that m[i] is null if count was never equal to i else it
is the index of
algo-
traverse the list from the end to find the 1. let the index of last 1 be x.
count=0;
while(i not equal to x or array_length )
if(a[i]==1)count++;
else count--;
print the value
i++;
while(--count)
printf("%d",a[i++]);
On Thu, Jul 22, 2010 at 5:53 PM, UMESH
Hello everybady,
my question is:-
Find the maximum length Subsequence in the given Array that contains
only 0's and 1's elements and condition is that number of 1;s equal to the
number of 0's.
Ex:-
Input:- 10101011100
output:-101010111000
--
You received this message because you are