Equilibrium index of a given sequence: What is the best algorithm to find one?

Equilibrium index of a sequence is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes. For example, in a sequence A:

A[0]=-7 A[1]=1 A[2]=5 A[3]=2 A[4]=-4 A[5]=3 A[6]=0

3 is an equilibrium index, because:

A[0]+A[1]+A[2]=A[4]+A[5]+A[6]

6 is also an equilibrium index, because:

A[0]+A[1]+A[2]+A[3]+A[4]+A[5]=0

(sum of zero开发者_开发技巧 elements is zero) 7 is not an equilibrium index, because it is not a valid index of sequence A. If you still have doubts, this is a precise definition: the integer k is an equilibrium index of a sequence if and only if and .

Assume the sum of zero elements is equal zero. Write a function

int equi(int[] A);

that given a sequence, returns its equilibrium index (any) or -1 if no equilibrium indexes exist. Assume that the sequence may be very long.

1. Calculate the total sum of all of the elements in A
2. For every index i, calculate the sum of the elements from A[0] to A[i - 1], until the sum is equal to (totalSum - A[i]) / 2.

Note that the sum of elements from A[0] to A[i - 1] can be tracked as a running total, which means that the complexity of the whole algorithm is O(n). Implementing as code is left as an exercise for the reader.

Here's a solution that uses O(n) memory. Compute S[i] = A[0] + A[1] + ... + A[i]. Then the sum of a subsequence [i, j] is Sum(i, j) = S[j] - S[i - 1] (S[x < 0] = 0).

So for each i from 0 to A.Length - 1 check if Sum(0, i - 1) = Sum(i + 1, A.Length - 1).

In fact, if you're allowed to destroy the given array, you don't even need S, you can do it all in A.

Pseudocode - worst case is 2 passes through A.

R = sum(A)
L = e = 0
for i = 0 .. A.size
  L+=e
  R-=(e=A[i])
  return i if L==R
end
return NULL

a = (-7, 1, 5, 2, -4, 3, 0)

sumleft = 0

sumright = 0

for i in range(len(a)):

for j in range(i+1,len(a)):

    sumright += a[j]

if sumright == sumleft:

    print i

sumleft += a[i]

sumright = 0