Rocky
BAN USER- 1of 1 vote
AnswersConsider an array of positive and negative integers. We want to
- Rocky
find a slice of this array (i.e. a sub‐array of consecutive elements) with at least two
elements, such that the sum of the elements in this slice is equal to 0. The size of the
slice can be anything (i.e. from 2 up to the length of the original array), and we don't
care about finding the first, last, shortest, or longest slice, we just want a slice.
Example: from [2,3,-1,2,-4] we would like to find the slice [3,-1,2,-4], where 3 + (-1) + 2 + (‐4) = 0| Report Duplicate | Flag | PURGE
Arrays
Solution was given by someone in the earlier posts like this:
Take another array of same size, at each position, fill in sum from ele at index 0 upto that position.
For example:
sum[0] = a[0]
sum[1] = sum[0] + {a[1]}
sum[2] = sum[1] + {a[2]}
and so on.
Now you want to find a duplicate value in this array. For that purpose, sort this 'sum' array. Find two consecutive values in this array which have same value.
For example:
sum[4] and sum[7] (in previous unsorted array, not the sorted one) may have same value, or any others.
Since these two values are same, it means sum of values between a[4] and a[7] should sum to 0. Precisely, (a[5] + a[6] + a[7]) should sum to zero here.
Thats it.
Complexity:
Time: O(n),
Space: O(n).
And someone suggested to check if any of the sum[i]s is also zero along with differences.. And this is true!
Now, can someone suggest a solution to the problem if the above question is extended asking you to find the longest(but not any) such slice??
@anonymous Now, take some medicine.. :D
- Rocky February 07, 2010The idea of sorting sum[] is actually given by someone to find the duplicates(i.e. "Find two consecutive values in this array which have same value" in the given explanation)
Now this can be achieved using a hashmap with O(n).. So, the time is given as O(n)