What follows are my solutions to Codility sample tasks. I did lots of both serious and stupid mistakes getting to decent solutions and my first submits were just sad. For the first one I forgot to return $-1$ in the case where there is no equilibrium index. For the second, this one took me the longest, I had forgotten I had to uncount repeated cases and returned the exception case way too early. I also did not know how to run binary searches using Python (at least now I know.) For the third, the easiest of them all, I was using a list instead of a dictionary as a checked bag and thus spending too much time asking if an element had been checked already while iterating over the list.
I felt that the expected complexity requirements for each problem end up giving up too much information about the nature of the solutions.
Note: Initially I only had the solution for three problems. I've continued practicing and I'll be adding solutions here as I go over each problem.
A zero-indexed array $A$ consisting of $N$ integers is given. An equilibrium index of this array is any integer $P$ such that $0 \leq 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] + \cdots + A[P−1] = A[P+1] + \cdots + 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$.
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.
Complexity:
def solution(A):
uppersum = sum(A)
lowersum = 0
term = 0
for i, x in enumerate(A):
lowersum += term
term = x
uppersum -= term
if lowersum == uppersum:
return i
return -1
Given an array $A$ of $N$ integers, we draw $N$ discs in a 2D plane such that the $I$-th disc is centered on $(0,I)$ and has a radius of $A[I]$. We say that the $J$-th disc and $K$-th disc intersect if $J \neq K$ and $J$-th and $K$-th discs have at least one common point.
Write a function def solution(A)
that, given an array $A$ describing $N$ discs as explained above, returns the number of pairs of intersecting discs.
The function should return $−1$ if the number of intersecting pairs exceeds $10^7$.
Complexity:
from bisect import bisect_right
def solution(A):
n = len(A)
upper = sorted([i + x for i, x in enumerate(A)])
lower = sorted([i - x for i, x in enumerate(A)])
counter = 0
for v in upper:
counter += bisect_right(lower, v)
counter -= n * (n + 1) / 2
if counter > 1e7:
return -1
return counter
A non-empty zero-indexed array $A$ consisting of $N$ integers is given. The first covering prefix of array $A$ is the smallest integer $P$ such that $0 \leq P < N$ and such that every value that occurs in array $A$ also occurs in sequence $A[0], A[1], \ldots, A[P]$.
Write a function def solution(A)
that, given a zero-indexed non-empty array $A$ consisting of $N$ integers, returns the first covering prefix of $A$.
Complexity:
def solution(A):
checked = {}
r = 0
for i, x in enumerate(A):
if not x in checked:
checked[x] = True
r = i
return r
A binary gap within a positive integer $N$ is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of $N$.
Write a function def solution(N)
that, given a positive integer $N$, returns the length of its longest binary gap. The function should return $0$ if $N$ doesn't contain a binary gap.
def solution(N):
zeros = bin(N)[2:].split('1')
zeros = zeros[:-1] # Just in case there are trailing zeros
return max(map(len, zeros))
A small frog wants to get to the other side of the road. The frog is currently located at position $X$ and wants to get to a position greater than or equal to $Y$. The small frog always jumps a fixed distance, $D$. Count the minimal number of jumps that the small frog must perform to reach its target.
Write a function def solution(X, Y, D)
that, given three integers $X$, $Y$ and $D$, returns the minimal number of jumps from position $X$ to a position equal to or greater than $Y$.
Complexity:
# This one is silly:
def solution(X, Y, D):
distance = Y - X
if distance % D == 0:
return (Y - X) / D
else:
return ((Y - X) / D) + 1 # Abussing Python's broken division.
A zero-indexed array $A$ consisting of $N$ different integers is given. The array contains integers in the range $[1\ldots(N + 1)]$, which means that exactly one element is missing.
Your goal is to find that missing element.
Write a function def solution(A)
that, given a zero-indexed array $A$, returns the value of the missing element.
Complexity:
def solution(A):
A = sorted(A) # The complexity is O(N log(N)), unfortunately. But Codility wasn't able to tell.
for i in range(len(A)):
if A[i] != i + 1:
return i + 1
return len(A) + 1
A non-empty zero-indexed array $A$ consisting of $N$ integers is given.
A permutation is a sequence containing each element from $1$ to $N$ once, and only once.
The goal is to check whether array $A$ is a permutation.
Write a function def solution(A)
that, given a zero-indexed array $A$, returns $1$ if array $A$ is a permutation and $0$ if it is not.
Complexity:
def solution(A):
n = len(A)
check = {i+1:False for i in xrange(n)}
for x in A:
if x not in check:
return 0
else:
if check[x] == True:
return 0
else:
check[x] = True
for x in check:
if check[x] == False:
return 0
return 1
Write a function def solution(A)
that, given a zero-indexed array $A$ consisting of $N$ integers, returns the number of distinct values in array $A$.
Complexity:
# Minimal solution
# A detailed version would require ordering the array
# and run over it while counting the times the value changes.
# (Which I guess is more or less the way Python turns a list into a set.)
def solution(A):
return len(set(A))
A string $S$ consisting of $N$ characters is called properly nested if:
Write a function def solution(S)
that, given a string $S$ consisting of $N$ characters, returns $1$ if string $S$ is properly nested and $0$ otherwise.
Complexity:
def solution(S):
stack = 0
for x in S:
if x == '(':
stack += 1
if x == ')':
stack -= 1
if stack < 0:
return 0
if stack == 0:
return 1
else:
return 0
You are given two non-empty zero-indexed arrays $A$ and $B$ consisting of $N$ integers. Arrays $A$ and $B$ represent $N$ voracious fish in a river, ordered downstream along the flow of the river.
The fish are numbered from $0$ to $N − 1$. If $P$ and $Q$ are two fish and $P < Q$, then fish $P$ is initially upstream of fish $Q$. Initially, each fish has a unique position.
Fish number $P$ is represented by $A[P]$ and $B[P]$. Array $A$ contains the sizes of the fish. All its elements are unique. Array $B$ contains the directions of the fish. It contains only $0$s and/or $1$s, where:
If two fish move in opposite directions and there are no other (living) fish between them, they will eventually meet each other. Then only one fish can stay alive − the larger fish eats the smaller one. More precisely, we say that two fish $P$ and $Q$ meet each other when $P < Q$, $B[P] = 1$ and $B[Q] = 0$, and there are no living fish between them. After they meet:
We assume that all the fish are flowing at the same speed. That is, fish moving in the same direction never meet. The goal is to calculate the number of fish that will stay alive.
Write a function def solution(A, B)
that, given two non-empty zero-indexed arrays $A$ and $B$ consisting of $N$ integers, returns the number of fish that will stay alive.
Complexity:
# First time I got 100% with my first submit.
def solution(A, B):
fish_downstream = []
up_survivors = 0
for i, direction in enumerate(B):
if direction == 1:
fish_downstream.append(A[i])
else:
is_active = 1
up = A[i]
while is_active:
if len(fish_downstream) != 0:
down = fish_downstream.pop()
if down > up:
fish_downstream.append(down)
is_active = 0
else:
is_active = 0
up_survivors += 1
return len(fish_downstream) + up_survivors
You have to climb up a ladder. The ladder has exactly $N$ rungs, numbered from $1$ to $N$. With each step, you can ascend by one or two rungs. More precisely:
Your task is to count the number of different ways of climbing to the top of the ladder.
Write a function def solution(A, B)
that, given two non-empty zero-indexed arrays $A$ and $B$ of $L$ integers, returns an array consisting of $L$ integers specifying the consecutive answers; position $I$ should contain the number of different ways of climbing the ladder with $A[I]$ rungs modulo $2^{B[I]}$.
Complexity:
def count_down(n, dicc):
for m in [1,2]:
if n-m in dicc:
dicc[n] = dicc.get(n,0)+dicc[n-m]
return dicc
def climbing_ways_counter(L):
dicc = {0:1}
for n in xrange(L):
count_down(n,dicc)
return dicc
def solution(A, B):
L = len(A) + 1
# Weird optimization trick. Modulo operation is too slow...
# Had to look up online for it:
B = [(1<<b)-1 for b in B]
d = climbing_ways_counter(L)
return [d[a] & b for a,b in zip(A,B)]