cant we just traverse once and count number of zeros and 1's
then store int k=min(n0ofzeros,noofone's)
then take two variables k1 = k2=0;;
i=0;
while(lengthofarray--){
if(s[i]==1){
cout<<"1";
k1++;
i++;
}
if(s[i]==0){
cout<<"0";
k2++;
i++;
}
if((k1==k)&&(k2==k))
break;
}
it will output maximum subsequence containing ualnum of zero's and 1's
On Mon, Jul 5, 2010 at 5:19 PM, Sateesh Pragallapati <
sateesh2sm...@gmail.com> wrote:
> I have 0(N) solution with O(N) space.
>
> void NumberOfZeros(int x[],int n)
> {
> int *postionIndex = new int[2*n +1];
> for(int i=0;i<2*n+1;++i)
> {
> postionIndex[i] = -1;
> }
>
> int index = 0;
> int maxWidth =0;
> int running =0;
> for (int i = 0; i <n; i++)
> {
> running = running + (x[i] == 0 ? 1:-1);
> if ( running == 0)
> {
> index = i;
> maxWidth = i+1;
> }
>
> int temp = running <0 ? n-running: running ;
> if ( postionIndex[temp] == -1)
> {
> postionIndex[temp] = i;
> }
> else if(i-postionIndex[temp] > maxWidth)
> {
> maxWidth = (i-postionIndex[temp]);
> index = i;
> }
>
> }
> cout<<"start = " << index-maxWidth+1 << " end = " << index << " diff = " <<
> maxWidth;
> }
>
> On Mon, Jul 5, 2010 at 4:31 PM, Ashish Goel <ashg...@gmail.com> wrote:
>
>> yes, i realised, there need to be one more for loop say over j for start
>> position taking values 1->n
>>
>> the second for loop as used should start from i=j to n
>>
>> so essentially it becomes nsquare
>>
>>
>> Best Regards
>> Ashish Goel
>> "Think positive and find fuel in failure"
>> +919985813081
>> +919966006652
>>
>>
>>
>> On Mon, Jul 5, 2010 at 2:42 PM, harit agarwal <agarwalha...@gmail.com>wrote:
>>
>>> @ashgoel
>>> check the output of your code here:
>>> http://codepad.org/7BSTedh5
>>>
>>> and i don't think this idea will work....
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
