CODEWITHSUNDEEP
c++algorithm
andre
andre

Reputation: 765

finding an index in array the gives a sum before and after it?

Given an array, I would like to find an index, that the numbers before it, and the numbers after it gives equal sum.

for example an array like [4,5,6,11,7,8]

output is index 3 because 4+5+6 = 7+8

Upvotes: 0

Views: 2702

Answers (3)

Saeed Amiri
Saeed Amiri

Reputation: 22555

First find sum of all items, save it as sum, then read from start of array and sum up items to arrive to (sum - current index value)/2, if you didn't get such result, means there isn't such an index, also if you get sum/2 in each index of iteration, means related index is your answer.

Sample: 4,5,6,11,7,8 sum = 41.

check index 0: currentSum  = 4, currentSum - currentValue = 4-4 != (41 - 4)/2
check index 1: currentSum  =  9, currentSum - currentValue = 9-5 != (41 - 5)/2
check index 2: currentSum  = 15, currentSum - currentValue = 15-6 != (41 - 6)/2
check index 3: currentSum  = 26, currentSum - currentValue = 15 == (41 - 11)/2

Upvotes: 3

user555045
user555045

Reputation: 64904

Create the (inclusive) prefix sum array (this takes O(n) steps)

Then for each index 0 < i < n, check whether prefixsum[i - 1] == prefixsum[n - 1] - prefixsum[i], return i if true. (also takes O(n) steps).

You can do this easier (and less space):

Calculate the sum of the array. O(n)

Then, going through the array, keep track of the prefix sum (exclusive, this time). Compare prefixsum == sum - (prefixsum + current). If true, return the current index. Also O(n).

Essentially it does the same as above, but avoids saving the prefix sums in an array.

Upvotes: 1

Justin
Justin

Reputation: 4216

Try building a Range Sum Segment Tree? Check each node, if their left/right children are equal then return it's index. Maybe overkill.

Upvotes: 0

Related Questions