LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#1 January 28 2013

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

Offline

#2 January 28 2013

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)

Offline

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

Offline

#4 January 28 2013

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

Offline

#5 January 30 2013

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]

Offline

Board footer