using extra space of O(n) we can do it in O(n^2) take an array for storing cumulative sums from index i till 0, then from i+1 till n-1 find summing each array value find whether it exists in array. if its so display indexes eg Array: 2,2,13,4,7,3,8,12,9,1,5 i = 3 ^ temp array: 4, 17, 19, 21 finding for cumulative sums from i+1 till i<=(any of values in temp array) i = 6 ^ temp array: 8, 11, 18, 22 finding for cumulative sums from i+1 till i<=(any of values in temp array) found values from i+1 till i+3 Repeating for every i,
surender On Mon, Jan 9, 2012 at 11:22 PM, priyanka jaggi <[email protected]>wrote: > Given an array (length n), we need to find the subarray (length k) such > that the sum of the first j elements of the subarray equals the sum of the > remaining (k-j) elements of the subarray. > For e.g. > Array: 2,2,13,4,7,3,8,12,9,1,5 > Output: 4,7,3,8,12,9,1 [4+7+3+8=12+9+1] > Could this be done with a complexity better than O(n^3) > k is not given . > > -- > 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.
