@Brijesh: +1 On Sun, Sep 11, 2011 at 2:14 PM, Brijesh <brijeshupadhyay...@gmail.com>wrote:
> This is the fastest way I can think of to do this, and it is linear to the > number of intervals there are. > > Let L be your original list of numbers and A be a hash of empty arrays > where initially A[0] = [0] > > sum = 0 > for i in 0..n > if L[i] == 0: > sum-- > A[sum].push(i) > elif L[i] == 1: > sum++ > A[sum].push(i) > > Now A is essentially an x y graph of the sum of the sequence (x is the > index of the list, y is the sum). Every time there are two x values x1 and > x2 to an y value, you have an interval (x1, x2] where the number of 0s and > 1s is equal. > > There are m(m-1)/2 (arithmetic sum from 1 to m - 1) intervals where the sum > is 0 in every array M in A where m = M.length > > Using your example to calculate A by hand we use this chart > > L # 0 1 0 1 0 0 1 1 1 1 0 > A keys 0 -1 0 -1 0 -1 -2 -1 0 1 2 1 > L index -1 0 1 2 3 4 5 6 7 8 9 10 > > (I've added a # to represent the start of the list with an key of -1. Also > removed all the numbers that are not 0 or 1 since they're just distractions) > A will look like this: > > [-2]->[5] > [-1]->[0, 2, 4, 6] > [0]->[-1, 1, 3, 7] > [1]->[8, 10] > [2]->[9] > > For any M = [a1, a2, a3, ...], (ai + 1, aj) where j > i will be an interval > with the same number of 0s as 1s. For example, in [-1]->[0, 2, 4, 6], the > intervals are (1, 2), (1, 4), (1, 6), (3, 4), (3, 6), (5, 6). > > Building the array A is O(n), but printing these intervals from A must be > done in linear time to the number of intervals. In fact, that could be your > proof that it is not quite possible to do this in linear time to n because > it's possible to have more intervals than n and you need at least the number > of interval iterations to print them all. > > Unless of course you consider building A is enough to find all the > intervals (since it's obvious from A what the intervals are), then it is > linear to n > > THis is the solution..go through it, its very easy to understand... > PS: copied from > > http://stackoverflow.com/questions/6967853/dynamic-programming-can-interval-of-even-1s-and-0s-be-found-in-linear-time > > > > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/wM8Xhc1tUXQJ. > > 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?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 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?hl=en.
