@pradip: Finding same element in temp array is little bit tricky. For displaying item from i+1 to j , you have to make sure that there is equal element at i and j index in temp array. How will you ensure it in O(n) time?
On Sun, Sep 2, 2012 at 3:16 PM, Pradeep Mishra <[email protected]>wrote: > This algorithm is *O(n)*. > > Given an int[] input array, you can create an int[] tmp array where tmp[i] > = tmp[i - 1] + input[i]; Each element of tmp will store the sum of the > input up to that element. > > Now if you check tmp, you'll notice that there might be values that are > equal to each other. Let's say that this values are at indexes j an k > with j < k, then the sum of the input till j is equal to the sum tillk and > this means that the sum of the portion of the array between j and k is 0! > Specifically the 0 sum subarray will be from index j + 1 to k. > > - NOTE: if j + 1 == k, then k is 0 and that's it! ;) > - NOTE: The algorithm should consider a virtual tmp[-1] = 0; > > Correct me if i am wrong Thanx > > -- > Pradeep Kumar Mishra > IIIT Allahabad > B. Tech 3rd Year ( IT ) > Another Mail - [email protected] > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
