Can you provide O(n) algo? On Sun, Sep 2, 2012 at 1:36 PM, Carl Barton <odysseus.ulys...@gmail.com>wrote:
> 1. Calculate the sum of every prefix of the array O(n) > 2. Store as pairs (sum, index) and sort by sum using a stable sort. > > Observation: Sum of every factor can be expressed as the difference > between the sum of 2 prefixes. > 3. for each entry search for the corresponding difference such the index > found is greater than original index. > > Works for any sum, not just 0. Takes O(n log n) > > > On 2 September 2012 14:22, Navin Kumar <algorithm.i...@gmail.com> wrote: > >> Given an unsorted integer array. Find the contiguous sub sequences whose >> sum is 0. >> >> -- >> 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/-/pFvfWQjVrnkJ. >> 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. > -- 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.
