A community for technology geeks in Lebanon.

You are not logged in.

- Topics: Active • Unanswered

Pages: **1**

**Joe****Member**

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.

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

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

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

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

```
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**

```
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]
```

Pages: **1**