CODEWITHSUNDEEP
algorithm
fittaoee
fittaoee

Reputation: 145

Find an element in array that equals to the sum of the remaining elements

I'm trying to think of an efficient algorithm that solves the following problem:

Given an array of integers, return the index of the element in the array that equals to the sum of the remaining elements in the array; if no such element exists, return -1.

For example, given the array of [1,2,3,6], then return 4 since 6=1+2+3; given [3, -3, 5, 1], return 0 since 3 = -3 + 5 + 1.

Any thoughts?

Upvotes: 0

Views: 524

Answers (1)

user4668606
user4668606

Reputation:

Solve this in two runs:

  • In the first run create the sum of all integers in the array
  • In the second run, check for each element i, whether arrSum == i * 2 holds - equivalent to arrSum - i == i. If it holds, you've found your searched element.

In code:

int sum = 0;
for(int i : arr)
    sum += i;

for(int i = 0 ; i < arr.length ; i++)
    if(sum == arr[i] * 2)
        return i;

return -1;

Runs in O(n).

Upvotes: 2

Related Questions