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:
6 is also an equilibrium index, because:
(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.
i, calculate the sum of the elements from
A[i - 1], until the sum is equal to
(totalSum - A[i]) / 2.
Note that the sum of elements from
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
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
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