i am just trying to think aloud, what if every position stored the number of
1s and number of zeros(explicit save not needed though)
so if o[i]=5, z[i]=5; then from 0->9 is the strong with equal seros
however if say o[i]=5 and z[i]=7 and o[j]=10 and z[j]=12, then j-i+1 is the
number of elements forming string with equal zeros and 1s
but htis is again o(n square) (:
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
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.
>
--
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.
