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.
