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 <[email protected]> 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 <[email protected]>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 [email protected].
>> To unsubscribe from this group, send email to
>> [email protected]<algogeeks%[email protected]>
>> .
>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> 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 [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.
