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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.