maintaining cumulative sums of left side of array from index i in in hash, and maintaining variable for right cumulative sums at each j ( j=i+1 till n-1) and check at each value on hash will solve in O(n^2), let me know if im wrong..
surender On Wed, Jan 11, 2012 at 9:12 PM, sravanreddy001 <[email protected]>wrote: > @Lucifer: a very good counter example involving the -ve numbers..[:)] > I never thought of negative numbers while looking for solution. > > And I don't see a O(N) solution for this --> > 1) Find the first pair (i,j) such that: > sum( A[0] .. till A[i]) = sum(B[0] ... B[i]) -- ESP when there > are -ve numbers, If No negative numbers its same as one provided before. > > And, sorting the sums & comparing them like you suggested leads us to > O(n^2 log n) > > -- > 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/-/4DoZ5nKZd5wJ. > > 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.
