**For programmers practicing their coding skills, or preparing to take a Codility assessment, we provide a series of free lessons, challenges and demo problems in our programmers' home. **

**One of the most popular tasks is Equi and to date we have evaluated over 50,000 solutions to this problem!**

The most popular language used for solving this problem is Java, although C#, PHP and C++ are also very popular:

**The problem description is very short:**

The 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

(The sum of zero elements is zero) 7 is not an equilibrium index - because it is not a valid index of sequence A. If you still have doubts, here is a precise definition: The integer k is an equilibrium index of a sequence A[0],A[1]..,A[n-1] if and only if

0<= kandsum(A[0..(k-1)])=sum(A[(k+1)..(n-1)]). Assume the sum of zero elements is equal to zero.Write a function

int equi(int A[], int n)that, given a sequence, returns its equilibrium index (any) or -1 if no equilibrium index exists. Assume that the sequence may be very long.

**The problem can be solved by using various approaches, the most common being simply to follow the equilibrium definition:**

int equi ( int A[], int n ) { int k, m, lsum, rsum; for(k = 0; k < n; ++k) { lsum = 0; rsum = 0; for(m = 0; m < k; ++m) lsum += A[m]; for(m = k + 1; m < n; ++m) rsum += A[m]; if (lsum == rsum) return k; } return -1; }

**Unfortunately, this approach has two disadvantages:**

- it fails on large input data sets, since the time complexity is
*O(n*^{2}) - it fails on large input values (for example if the input array contains values like MIN/MAX_INT) due to the arithmetic overflows

The solution analysis will detect such problems in submitted code:

We can fix the first problem with a better algorithm, and the second problem with a better data-type (for example, using long long type instead of int for sum computations). The key observation for better running time is to update the left/right sums in constant time instead of recomputing them from the scratch.

int equi(int arr[], int n) { if (n==0) return -1; long long sum = 0; int i; for(i=0;i<n;i++) sum+=(long long) arr[i]; long long sum_left = 0; for(i=0;i<n;i++) { long long sum_right = sum - sum_left - (long long) arr[i]; if (sum_left == sum_right) return i; sum_left += (long long) arr[i]; } return -1; }

**Using this solution, you can obtain a perfect score:**

**What's next?**

We have a live competition to write the shortest Equi solution - 54 bytes is smallest solution to date! If you're preparing for a Codility assessment, we offer two other demo problems which are free to take and can help you warm up:

Happy coding and good luck!

Itumeleng Ntshoe

Hi,
I'd like to join the group in order to better my problem solving skills and learn to solve more complex problems using different algorithms.
Regards
Itumeleng

Jeffrey Swartwout

Hi Itumeleng,
Just click "Join our free Programmers' Home" above to join! Best of luck honing your problem-solving skills!
Best,
Jeff

Solutions for our Equi Task
Mar 25, 2011

Front-end and Back-end: The Art of Hiring Developers
Jun 21, 2017