Projects > Codility Problems

Here is another project to improve my programming skills. Codility is a software company that specializes in code testing. That is, they provide problems for which you have to write code to solve, after you submit your code, they analyze it and grade it for you.

Currently they have three demo exercise which can be attempted by anyone. There are also monthly coding challenges that are quite difficult but reward the person who can solve the challenge flawlessly with a certificate. I will attempt those too and post the certificates when i get them!

Please note that the main reason I am doing this is to learn! If you find any mistake in my solution, please don't hesitate to contact me.

I will solve the problems in more than one programming language, initially though, i will start with Python 3. Furthermore, i will post the evaluation report provided by Codility for each.

Please choose the problem from the box below:

Problem Description:

Description on Codility

A zero-indexed array A consisting of N integers is given. An equilibrium index of this array is any integer P such that 0 ≤ P < N and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e.

	A[0] + A[1] + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1]. 

Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N−1.

For example, consider the following array A consisting of N = 7 elements:

	A[0] = -7   A[1] =  1   A[2] = 5
	A[3] =  2   A[4] = -4   A[5] = 3
	A[6] =  0

P = 3 is an equilibrium index of this array, because:

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

P = 6 is also an equilibrium index, because:

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

and there are no elements with indices greater than 6.

P = 7 is not an equilibrium index, because it does not fulfill the condition 0 ≤ P < N.

Write a function

def solution(A)

that, given a zero-indexed array A consisting of N integers, returns any of its equilibrium indices. The function should return −1 if no equilibrium index exists.

Assume that:

• N is an integer within the range [0..10,000,000];
• each element of array A is an integer within the range [−2,147,483,648 .. 2,147,483,647].

For example, given array A such that

	A[0] = -7   A[1] =  1   A[2] = 5
	A[3] =  2   A[4] = -4   A[5] = 3
	A[6] =  0

the function may return 3 or 6, as explained above.

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Code:

• Python

def solution(A):
    """Finds the equilibrium index of a list of integers.
    
    Given a zero-indexed array A consisting of N integers, returns any of
    its equilibrium indices. The function should return -1 if no
    equilibrium index exists.

    """
    
    array_length = len(A)

    if (array_length < 1): return -1

    if (array_length < 2): return 0

    #Accumulator to store sum so far
    accumulator = 0

    adjusted_sum = sum(A)

    for i in range(0, (array_length)):

        adjusted_sum -= A[i]

        if (accumulator == adjusted_sum):
            return i

        accumulator += A[i]

    return -1
    

Codility Evaluation: