**22**
04/11

13:41

## Finding equilibrium

Carlos shared a pretty cool link with me this morning. Codility is a platform to help recruiters and contractors to test developers before hiring them. Both the idea and the execution are beautiful. They’ve done a stunning job.

As part of my visit to the page I gave a try to the demo test. As it was fun to solve it, I’m sharing my solution here. The problem was quite easy. It reads like this:

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.

Assume the sum of zero elements is equal zero. Write a function int equi(int[] A); that given a sequence, returns its equilibrium index (

any) or -1 if no equilibrium indexes exist.Assume that the sequence may be very long.

They gave me 30 minutes to design, code and test my solution. Here it is (tests omitted):

import operator def equi(A): if A is None or len(A) == 0: return -1 lsum = index = 0 rsum = reduce(operator.add, A[1:], 0) while True: if lsum == rsum: return index index += 1 if index == len(A): return -1 else: lsum += A[index-1] rsum -= A[index] |

It scores 100/100 and runs in linear time (that’s tricky because O(n^{2}) algorithms will cause performance tests to fail) :)