• Coding

  • [Exercise] Equilibrium index

You are given an array A consisting of N integers. We define equilibrium index as a number P such as:
  • 0 <= P <N # A is zero-indexed
  • A[0] + A[1] + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1]
Note that the sum of zero elements is assumed to be equal to 0.

Example 
A = [9, -3, 5, -15, 4, 0, 7]
P = 3 is an equilibrium index because 
>>> 9 - 3 + 5 == 4 + 0 + 7
True
P = 6 is another equilibrium index: 
>>> 9 - 3 + 5 - 15 + 4 + 0 == 0    # note that 6 is the greatest index of A
True
Exercise
Write a function which takes the array as argument and returns the set of equilibrium indexes the array has. (As usual, an "array" can be any ordered collection of elements you want).

Bonus points
If your code's worst case space and time complexities are both O(N).
Here's a dirty one liner in Python, for each element in the list compare the sum of the left sub list with the right one. 
eq_index = lambda A:[x for x in xrange(len(A)) if sum(A[:x]) == sum(A[x+1:])]
O(N) in time and space in C++: 
#include <iostream>

using namespace std;

int main()
{
    int A[]={9, -3, 5, -15, 4, 0, 7};
    int size=7,leftSum=0,rightSum=0;
    for(int i=1;i<size;i++)
    {
        rightSum+=A[i];
    }
    for(int i=0;i<size;i++)
    {
        if(rightSum==leftSum)
            cout << i << " is an equilibrium index of A" << endl;
        if(i+1<size)
            rightSum-=A[i+1];
        leftSum+=A[i];
    }
    return 0;
}

A = {9, -3, 5, -15, 4, 0, 7};
Position[Most@FoldList[Plus, 0, A] - Rest@Reverse@FoldList[Plus, 0, Reverse@A], 0]

{{4}, {7}}

A = Array[0 &, 10];
Position[Most@FoldList[Plus, 0, A] - Rest@Reverse@FoldList[Plus, 0, Reverse@A], 0]

{{1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}, {10}}

def equi_idx(A):
    total_sum = sum(A)

    return [i for i in range(len(A))
            if sum(A[:i]) == (total_sum - A[i]) / 2.0]