LebGeeks

Joe

Member

[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).

Ayman

Member

Re: [Exercise] Equilibrium index

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:])]

Last edited by Ayman (January 28 2013)

Ra8

Member

Re: [Exercise] Equilibrium index

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;
}

geek

Member

Re: [Exercise] Equilibrium index

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}}

Joe

Member

Re: [Exercise] Equilibrium index

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]