# language agnostic - what is the best algorithm to use for this problem

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=-7 A=1 A=5 A=2 A=-4 A=3 A=0``

3 is an equilibrium index, because:

``A+A+A=A+A+A``

6 is also an equilibrium index, because:

``A+A+A+A+A+A=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` to `A[i - 1]`, until the sum is equal to `(totalSum - A[i]) / 2`.

Note that the sum of elements from `A` 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 + A + ... + 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
``````