Equilibrium index of a sequence

Question

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[0]=-7 A[1]=1 A[2]=5 A[3]=2 A[4]=-4 A[5]=3 A[6]=0

3 is an equilibrium index, because:

A[0]+A[1]+A[2]=A[4]+A[5]+A[6]

6 is also an equilibrium index, because:

A[0]+A[1]+A[2]+A[3]+A[4]+A[5]=0

(sum of zero elements is zero) 7 is not an equilibrium index, because it is not a valid index of sequence A.

The idea is to create a program that given a sequence (array), returns its equilibrium index (any) or -1 if no equilibrium indexes exist.

Answer 1

Golfscript 17 16

Since the form of the input isn't specified, this takes a string in Golfscript array format from stdin.

~0\{1$+.@+\}/])?

So run as e.g.

golfscript.ry eqindex.gs <<<"[-7 1 5 2 -4 3 0]"

The idea is very simple: it takes an array of A_i and maps to an array of A_i + 2 SUM_{j<i} A_j and then looks for the first index which is equal to the sum of the whole array.

---

For @mellamokb's challenge I offer:

~0\{1$+.@+\}/:S;]:A,,{A=S=},`

for 29 chars.

Answer 2

Python - 72 chars

A=input()
print[i for i in range(len(A))if sum(A[:i])==sum(A[i+1:])]or-1

Takes comma separated input

Answer 3

Haskell (95 83)

e l=[n|n<-[0..length l-1],sum(take n l)==sum(drop(n+1)l)]
main=interact$show.e.read

Reads a list in Haskell style from stdin, eg.

[-7,1,5,2,-4,3,0]

and returns a Haskell style list of the indices, eg.

[3,6]

The result is [], if there is no index.

Please tell me, if your spec wants a different behavior.

Edits:

• (95 → 83): list comprehension is more breve

Answer 4

C - 96

a[99],*p=a,s;main(){for(;scanf("%d",p)>0;s+=*p++
);for(;p>a;s-=*p)(s-=*--p)||printf("%d\n",p-a);}

Note that this prints the equilibrium indices in reverse order.

Sample usage:

$ ./equilibrium <<< "-7 1 5 2 -4 3 0"
6
3

Answer 5

Ruby (83 77)

a=*$<.map(&:to_i)
p (0...a.size).select{|x|a[0..x].reduce(:+)==a[x..-1].reduce(:+)}

Edit: Shorter version as suggested by Ventero:

a=$<.map &:to_i
p (0...a.size).select{|x|eval"#{a[0..x]*?+}==#{a[x..-1]*?+}"}

Input is one number per line, output is comma separated list of indexes in square brackets.

Answer 6

JavaScript (161)

P=parseInt;L=prompt().split(',');S=function(A)A.reduce(function(a,b)P(a)+P(b),0);R=[i for(i in L)if(S(L.slice(0,i))==S(L.slice(P(i)+1)))];alert(R.length>0?R:-1);

http://jsfiddle.net/6qYQv/1/

Answer 7

scala, 108

val l=readline().split(" ").map(w=>w.toInt)
for(i<-0 to l.length-1
if l.take(i).sum==l.drop(i+1).sum)yield i

Answer 8

J (12 characters)

A monadic verb in tacit notation that returns a vector of equilibrium indices. Spaces inserted for legibility only.

[: I. +/\. = +/\

To explain this, first observe its explicit definition; y is the formal parameter:

3 : 'I. (+/\. y) = (+/\ y)'

• + adds its arguments. / is an adverb that inserts the verb left of it between the members of its right argument, e.g. +/ 1 2 3 4 is the same as 1 + 2 + 3 + 4.

• \ is an adverb that applies the verb to its left to all prefixes prefixes of its right argument. For instance, with < drawing a box around its argument, <\ 1 2 3 4 produces

  ┌─┬───┬─────┬───────┐
  │1│1 2│1 2 3│1 2 3 4│
  └─┴───┴─────┴───────┘
  

• Thus, +/\ computes for each prefix of its right argument the sum.

• \. is like \ but operates on suffixes instead of prefixes. Thus, +/\. computes a vector of sums of suffixes.
• = performs item-wise comparison of its arguments. For instance, 1 1 3 3 = 1 2 3 4 yields 1 0 1 0.
• Thus, (+/\. y) = (+/\ y) yields one for all indices at which the suffix sum is equal to the prefix sum, or, an equilibrium is created.
• For vectors of zeroes and ones, I. returns a vector of the indices at which the vector contains a one.

Answer 9

Python 2, 70

A=input()
e=i=s=0
for x in A:e=[e,~i][s*2==sum(A)-x];s+=x;i+=1
print~e

The idea is to track the running sum s and check whether it is half of the sum of array without the current element, and therefore equal to the sum of the array after the current element. If so, we update the equilibrium index to the current index. The last equilibrium index is printed, or the initial value -1 if there's none.

Actually, we store the bit-complement of the equilibrium index so that we can initialize it to 0 instead.

Answer 10

Python - 114

i=map(lambda x:int(x),raw_input().split(" "));x=0
print map(lambda x:(sum(i[0:x])==sum(i[x+1::])),range(0,len(i)))

Python - 72

i=input()
print map(lambda x:sum(i[0:x])==sum(i[x+1::]),range(0,len(i)))

Prints whether or not the given index is an equilibrium index, does not print the integer indecies at which the array is balanced.

Answer 11

PHP, 134 chars

<?for($a=explode(",",fgets(STDIN));++$i<($c=count($a));$o.=$s==0?$i:"")for($n=$s=0;$n<$c;)$s+=$n<$i?$a[$n++]:-$a[++$n];echo$o?$o:"-1";

I have an itch that this is far from optimal PHP golfing, but just ran out of steam (brains). At least it's shorter than with array_sum and array_splice :-)

Answer 12

PHP (81)

for($i=count($a)-1,$c=0;$i+1&&$c!=(array_sum($a)-$a[$i])/2;$c+=$a[$i--]);echo $i;

http://3v4l.org/qJvhO

Since no input was specified, this needs to be initialised with the array as the variable $a.