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> > >>> . > >>> 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. > > > -- > > 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> > > . > > 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.
