for such problems, assign 1 to 1 and -1 to 0
int start_index=0;
int end_index=0;
int new_start_index=start_index;
int new_end_index=end_index;
int arr[size] = {0};//size represents number of bits
int sum=0;
for (int(i=0;i<size;i++)
{
if (a[i]& (1<<i)==0) //ith bit is zero
{sum -=1; }
else sum +=1;
if (sum == 0)
{//string of equal zeros and 1s found check if it is greater than
the previous one
if (new_start_index - end_index ==1)
{
end_index = i;
}
else if ( new_end_index - new_start_index > end_index -
start_index)
{
start_index = new_start_index;
end_index = i;
}
new_start_index = i+1;
new_end_index = new_start_index;
}
}
if (start_index != end_index)
printf("the longest string with equal number of zeros and 1s is
starting @%d and ending at %d, start_index, end_index);
}
sharad kumar wrote:
> You are given an array ' containing 0s and 1s. Find O(n) time and O(1) space
> algorithm to find the maximum sub sequence which has equal number of 1s and
> 0s.
>
> Examples
> 1) 10101010
> The longest sub sequence that satisfies the problem is the input itself
>
> 2)1101000
> The longest sub sequence that satisfies the problem is 110100
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
