Agree, the true answer is [0,7]. My previous post happened to be incorrect illustration of a correct program, as the attached code returns 0,7 only. The code (correctly) assumes a hidden 0 at *diff [-1]* always, so the longest interval that can be retained is (0,7) in this case.
On Wed, Nov 3, 2010 at 10:47 PM, Soumya Prasad Ukil <ukil.sou...@gmail.com>wrote: > why not the answer (0,7)? > > On Nov 1, 4:02 pm, sumant hegde <sumant....@gmail.com> wrote: > > Say diff [i] = (no. of 1s in B[ 0...i ]) - (no. of 1s in A[0...i]). In > other > > words the subarray B(0,i) contains diff(i) no. of more 1s than the > subarray > > A[0,i]. And diff[i] < 0 indicates the excess of 1s in A's subarray. > > Ex > > A: 0 1 1 0 0 0 1 1 1 1 > > B: 1 0 0 0 1 1 0 1 0 0 > > diff:1 0 -1 0 0 1 0 0 -1 -2 > > If diff[n-1] were 0, the answer would be whole array (interval 0,n-1). > > but it's actually -2, so I may want to chop off a segment (or 2 segments > > from both ends) such that the retained interval should be the longest. > > For that I look for two instances of an element in diff which yield the > > longest interval. In the example it's two -1's (alternatively two zero's > at > > diff[1] & diff[7] also work). Ignore the left-side -1. Thus the final > > interval is (3,8). > > This works because, A[0..8] had one extra 1,(which is what diff[8]=-1 > tells) > > which is balanced by removing the segment A[0..2] (which too contained an > > extra 1, again by diff[2]=-1). > > > > On Mon, Nov 1, 2010 at 3:49 PM, sunny agrawal <sunny816.i...@gmail.com > >wrote: > > > > > @sumanth > > > can you plz post algorithm in short. > > > > > On Mon, Nov 1, 2010 at 3:45 PM, sumant hegde <sumant....@gmail.com> > wrote: > > > > >> see attached file > > > > >> On Sun, Oct 31, 2010 at 4:27 PM, snehal jain <learner....@gmail.com > >wrote: > > > > >>> Find longest interval:- > > >>> We are given with two arrays A and B..each of size > > >>> N...elements of array contains either 1 or 0... > > >>> we have to find such an interval (p,q)(inclusive) such that the sum > of > > >>> all > > >>> the elements of A (between this interval) and sum of all elements of > > >>> B > > >>> (between this interval ) is equal... > > >>> i.e. > > >>> a[p]+a[p+1]....+a[q]= b[p]+b[p+1]....+b[q] > > > > >>> -- > > >>> 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> > <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@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> > <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com> > > > > >> . > > >> For more options, visit this group at > > >>http://groups.google.com/group/algogeeks?hl=en. > > > > > -- > > > Sunny Aggrawal > > > B-Tech IV year,CSI > > > Indian Institute Of Technology,Roorkee > > > > > -- > > > 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> > <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@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.
