Codility has a number of lessons online to help candidates prepare for the problems on the site. I figured it might be worthwhile to make a summary of some of the algorithms from the lessons that I more easily forget.

Prefix (and suffix) sums

Makes it easy to calculate totals for slices of an array. Codility provides the following algorithm:

def prefix_sums(A):
    n = len(A)
    P = [0] * (n + 1)
    for k in range(1, n + 1):
        P[k] = P[k - 1] + A[k - 1]
    return P

Note that the first element is 0 with this algorithm.

The sum of the elements in a slice from x to y can be calculated using P[y + 1] - P[x].

Leader of an array

The leader of an array is the element that occurs more than \(\frac{n}{2}\) times in the array. Codility provides the following \(O(n)\) solution for this:

def goldenLeader(A):
    n = len(A)
    size = 0
    # keep a 'stack' of leaders to find a potential candidate
    for k in xrange(n):
        if (size == 0):
            size += 1
            value = A[k]
        else:
            if (value != A[k]):
                size -= 1
            else:
                size += 1

    # validate that the candidate is actually the leader    
    candidate = -1
    if (size > 0):
        candidate = value
    leader = -1
    count = 0
    for k in range(n):
        if (A[k] == candidate):
            count += 1

    if(count > n // 2):
        leader = candidate

    # returns -1 if no leader was found
    return leader

Maximum slice

Finds the slice with the largest sum. Codility provides an implementation of Kadane’s algorithm for this problem:

def golden_max_slice(A):
    max_ending = max_slice = 0
    for a in A:
        max_ending = max(0, max_ending + a)
        max_slice = max(max_slice, max_ending)
    return max_slice

Initialisation doesn’t have to start from 0 and Wikipedia has more information on variations of the algorithm.

Counting divisors of \(n\)

Codility provides an algorithm that can count divisors of \(n\) in \(O(\sqrt{n})\). It relies on finding symmetric divisors, which allows you to count two divisors for the price of one.

def divisors(n):
    i = 1
    result = 0
    # iterate up to sqrt(n)
    while (i * i < n):
        if (n % i == 0):
            result += 2
        i += 1
    # if i^2 == n, then we count an extra divisor
    if (i * i == n):
        result += 1
    return result

Checking for prime numbers

Based on the same principles as the example above, you can check for primes by iterating over i * i <= n. If n % i == 0, then the number isn’t prime.

Sieve of Eratosthenes

Can be used to find all prime numbers in the range \(2\) to \(n\).

Here’s an implementation based on Codility’s notes.

Some quick reminders:

Need a list of flags for each number from 2 to n.
Main loop iterates from 2 to \(\sqrt{n}\) (inclusive). Not necessary to iterate all the way to n.
Each time the main loop is incremented, if the flag for the current value i indicates it is still prime:
1. Mark \(i^2\) as non prime.
2. Mark \(i^2 + i\) as non prime.
3. Continue marking multiples as non prime until reaching n.
At the end, all prime numbers will have been found.
Complexity is \(O(n\log{\log{n}})\).

Finding prime factors

The Sieve of Eratosthenes algorithm can be modified to find the prime factors of a number n.

Build an array F of minimum prime factor for each value of i instead of just using true/false.
Iterate through this array starting at element n.
Store the prime factor at position F[n] in the output list of prime factors.
n = n / F[n]
Keep iterating until F[n] == 0

Complexity is \(O(\log{n})\).

See here for an implementation based on Codility’s notes.

Euclidean algorithm

The Codility notes provide 3 approaches for finding the greatest common divisor (gcd) between 2 numbers:

Euclidean algorithm by subtraction: recursively subtract the larger value from the smaller until the values are equal. \(O(n)\)
Euclidean algorithm by division: recursively use the modulo operator until the two values are divisible by each other. \(O(\log(a + b))\) where \(a\) and \(b\) are the two input values.
Binary Euclidean algorithm: a more complex implementation involving division by 2 and scaling the result. \(O(\log{n})\)

The least common multiple (lcm) of \(a\) and \(b\) is the smallest value that can be divided by \(a\) and \(b\).

\[lcm(a, b) = \frac{a \cdot b}{gcd(a, b)}\]

See here for an implementation based on Codility’s notes.

Fibonacci numbers

def fib(n):
    fib = [0] * (n + 2)
    fib[1] = 1

    for i in range(2, n + 1):
        fib[i] = fib[n - 1] + fib[n - 2]
    
    return fib[n]

Complexity is \(O(n)\).

Binary search

Start with a sorted list of values v, length n. beg = 0, end = n - 1, \({ mid = \lfloor\frac{beg + end}{2}}\rfloor\). Compare the value of v[mid] to x, and set beg or end to mid ± 1 depending on the value. Keep repeating until x has been found (or can’t be found).