let A[i+1] = a[0] + a[1] + ... + a[i]; let B[i+1] = b[0] + b[1] + ... + b[i]; A[0] = B[0] = 0; sum of nos from i to j of a[] = A[j+1] - A[i]; // O(1) time
Thus O(n^2) sol can be obtained for this problem by finding the sub-array sum in the range [i, j] for every i, j; But I have not used the fact that the given nos is either 0 or 1. There should be a better way, yet to think about it :) 2009/8/26 ankur aggarwal <ankur.mast....@gmail.com> > 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] > > > > -- "Reduce, Reuse and Recycle" Regards, Vivek.S --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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 -~----------~----~----~----~------~----~------~--~---
