01/19/16

# Codility ‘CyclicRotation’ Solution

##### Short Problem Definition:

Rotate an array to the right by a given number of steps.

Cyclic Rotation

##### Complexity:

expected worst-case time complexity is O(N)

##### Execution:

There are multiple solutions to this problem. I picked the one that does not create a copy of the array.

##### Solution:
```def reverse(arr, i, j):
for idx in xrange((j - i + 1) / 2):
arr[i+idx], arr[j-idx] = arr[j-idx], arr[i+idx]

def solution(A, K):
l = len(A)
if l == 0:
return []

K = K%l

reverse(A, l - K, l -1)
reverse(A, 0, l - K -1)
reverse(A, 0, l - 1)

return A
```

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

06/30/15

# Codility ‘TrekAndSwim’ 2015 Argon Solution

##### Short Problem Definition:

Find a longest slice of a binary array that can be split into two parts: in the left part, 0 should be the leader; in the right part, 1 should be the leader.

Trek and Swim

##### Complexity:

expected worst-case time complexity is O(N)

expected worst-case space complexity is O(N)

##### Execution:

The PHP solution is by Rastislav Chynoransky. The Python code and an execution explanation will follow shortly.

##### Solution:
```/**
* @author Rastislav Chynoransky
*/
function solution(\$A) {
\$sum = 0;
for (\$i = 0; \$i < count(\$A); \$i++) {
\$sum += !\$A[\$i];
\$zeros[] = \$sum;
}

\$sum = 0;
for (\$i = count(\$A); \$i--;) {
\$sum += \$A[\$i];
\$ones[\$i] = \$sum;
}

for (\$i = count(\$A) - 1; \$i--;) {
\$res[\$i] = (\$zeros[\$i] + \$ones[\$i]) * (\$A[\$i + 1] - \$A[\$i]);
}

\$max = max(\$res);

if (\$max <= 0) {
return 0;
}

\$index = array_search(\$max, \$res);

\$right = 0;
\$sum = 0;
for (\$i = \$index + 1; \$i < count(\$A); \$i++) {
\$sum += \$A[\$i];
if (2 * \$sum / (\$i - \$index) > 1) {
\$right = \$i - \$index;
}
}

\$left = 0;
\$sum = 0;
for (\$i = \$index; \$i >= 0; \$i--) {
\$sum += !\$A[\$i];
if (2 * \$sum / (\$index - \$i + 1) > 1) {
\$left = \$index - \$i + 1;
}
}

return \$left + \$right;
}
```

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

05/7/15

# Codility ‘SqlSegmentsSum’ Kalium 2015 Solution

##### Short Problem Definition:

Compute the total length covered by 1-dimensional segments.

SqlSegmentSum

time complexity

space complexity

##### Execution:

I first create a numbers table from 1 to 1.000.000, this could be done just once when creating the DB. In this challenge it adds a flat 0.3sec runtime to all testcases.

In the second step I simply unique join the segments and number tables.

##### Solution:
```-- create numbers utility structure, very basic integer primary key column n
create table numbers(n integer not null, primary key(n asc));
-- insert generated sequential integers
insert into numbers(n)
select rowid
from (

-- build 1,000,000 rows using Cartesian product
select 1
from (
select 0 union select 1 union select 2 union select 3
union select 4 union select 5 union select 6
union select 7 union select 8 union select 9
) a, (
select 0 union select 1 union select 2 union select 3
union select 4 union select 5 union select 6
union select 7 union select 8 union select 9
) b, (
select 0 union select 1 union select 2 union select 3
union select 4 union select 5 union select 6
union select 7 union select 8 union select 9
) c, (
select 0 union select 1 union select 2 union select 3
union select 4 union select 5 union select 6
union select 7 union select 8 union select 9
) d, (
select 0 union select 1 union select 2 union select 3
union select 4 union select 5 union select 6
union select 7 union select 8 union select 9
) e, (
select 0 union select 1 union select 2 union select 3
union select 4 union select 5 union select 6
union select 7 union select 8 union select 9
) f

) derived;

select count(distinct n) from numbers inner join segments
on numbers.n between segments.l+1 and segments.r
```

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

05/7/15

# Codility ‘CannonBalls’ 2012 Chi Solution

##### Short Problem Definition:

Simulate a cannon shooting and heaps of falling cannonballs

Cannon Balls

##### Complexity:

expected worst-case time complexity is O(H+M+N)

expected worst-case space complexity is O(H+M)

##### Execution:

The obvious brute force solution would be to check the minimum index that is high enough to block the shot. This would result in a N*M runtime. Based on observation we can see that the hit location can be precomputed and it changes only with small steps.

• -1 in the hit_location means, that the ball either ricochets or flies above the highest peak
• anything that hits the 0th index also does nothing
##### Solution:
```def solution(A, B):
highest_ball = max(B)
hit_location = [-1] * (highest_ball+1)
ricochet = A

for idx, a in enumerate(A):
lvl = min(a, highest_ball)
while hit_location[lvl] == -1 and lvl > ricochet:
hit_location[lvl] = idx
lvl -= 1

# print hit_location

for ball in B:
hits_at = hit_location[ball]
# print "ball", ball, "hits at", hits_at
if hits_at <= 0:
continue
A[hits_at-1] += 1
hit_location[A[hits_at-1]] = min(hit_location[A[hits_at-1]], hits_at-1)

return A
```

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

04/27/15

# Codility ‘NumberOfDiscIntersections’ 2010 Beta Solution

##### Short Problem Definition:

Compute intersections between sequence of discs.

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 ≠ K and J-th and K-th discs have at least one common point.

Number of Disc Intersections

##### Complexity:

expected worst-case time complexity is O(N*log(N))

expected worst-case space complexity is O(N)

##### Execution:

In my mind this problem is very similar to the Codility Fish. You keep count of how many not-yet-ended disks there are. Every beginning has to cross all not-yet-ended disks. The best explanation on the web was written by Luca. His solution is much better than my C-style double-checked while loop. I therefore created a mixture of both 🙂

• Keep in mind that any pair of circles can intersect only once.
• If 1+ beginnings have the same point as 1+ endings. You first have to process the beginnings. The old and new ones have per definition a meeting point.
##### Solution:
```def solution(A):
circle_endpoints = []
for i, a in enumerate(A):
circle_endpoints += [(i-a, True), (i+a, False)]

circle_endpoints.sort(key=lambda x: (x, not x))

intersections, active_circles = 0, 0

for _, is_beginning in circle_endpoints:
if is_beginning:
intersections += active_circles
active_circles += 1
else:
active_circles -= 1
if intersections > 10E6:
return -1

return intersections
```

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

04/24/15

# Codility ‘PrefixSet’ 2010 Alpha Solution

##### Short Problem Definition:

Given a table A of N integers from 0 to N-1 calculate the smallest such index P, that that {A,…,A[N-1]} = {A,…,A[P]}.

PrefixSet

##### Complexity:

expected worst-case time complexity is O(N)

expected worst-case space complexity is O(N)

##### Execution:

Based on the number of elements that can occur in N, you either mark the occurrences in a boolean array, or put them in a set. The last occurrence of an element that was not seen before is the result.

##### Solution:
```def solution(A):
seen = set()
smallest_prefix_idx = 0

for idx in xrange(len(A)):
if A[idx] not in seen:
smallest_prefix_idx = idx

return smallest_prefix_idx
```

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

03/13/15

# Codility ‘Max Nonoverlapping Segments’ Solution

##### Short Problem Definition:

Find a maximal set of non((-))overlapping segments.

MaxNonoverlappingSegments

##### Complexity:

expected worst-case time complexity is O(N)

expected worst-case space complexity is O(N)

##### Execution:

This can be solved by using greedy search. The beginning of the next segment must come strictly after its predecessor.

##### Solution:
```def solution(A, B):
if len(A) < 1:
return 0

cnt = 1
prev_end = B

for idx in xrange(1, len(A)):
if A[idx] > prev_end:
cnt += 1
prev_end = B[idx]

return cnt
```

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

01/6/15

# Codility ‘MaxSliceSum’ Solution

##### Short Problem Definition:

Find a maximum sum of a compact subsequence of array elements.

MaxSliceSum

##### Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N)

##### Execution:

The only difference to the example given by Codility is the minimal slice length, which is 1.

##### Solution:
```def solution(A):
max_ending = max_slice = -1000000
for a in A:
max_ending = max(a, max_ending +a)
max_slice = max(max_slice, max_ending)

return max_slice
```

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

01/5/15

# Codility ‘CountNonDivisible’ Solution

##### Short Problem Definition:

Calculate the number of elements of an array that are not divisors of each element.

CountNonDivisible

##### Complexity:

expected worst-case time complexity is O(N*log(N));

expected worst-case space complexity is O(N)

##### Execution:

Using the Sieve of Eratosthenes, you generate divisors for all input elements of A. If a given number x is a divisor of element (x*N == element), then N also is a divisor. (N = element//x). After all divisors are computed, we simply subtract those (multiplied by their counts or 0) from the total number of elements in A.

##### Solution:
```def solution(A):

A_max = max(A)

count = {}
for element in A:
if element not in count:
count[element] = 1
else:
count[element] += 1

divisors = {}
for element in A:
divisors[element] = set([1, element])

# start the Sieve of Eratosthenes
divisor = 2
while divisor*divisor <= A_max:
element_candidate = divisor
while element_candidate  <= A_max:
if element_candidate in divisors and not divisor in divisors[element_candidate]:
element_candidate += divisor
divisor += 1

result =  * len(A)
for idx, element in enumerate(A):
result[idx] = (len(A)-sum([count.get(divisor,0) for divisor in divisors[element]]))

return result
```

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

01/2/15

# Codility ‘MinAvgTwoSlice’ Solution

##### Short Problem Definition:

Find the minimal average of any slice containing at least two elements.

MinAvgTwoSlice

##### Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N)

##### Execution:

Every slice must be of size two or three. Slices of bigger sizes are created from such smaller slices. Therefore should any bigger slice have an optimal value, all sub-slices must be the same, for this case to hold true. Should this not be true, one of the sub-slices must be the optimal slice. The others being bigger. Therefore we check all possible slices of size 2/3 and return the smallest one. The first such slice is the correct one, do not use <=!

For other languages use BigInts or equal. This line (A[idx] + A[idx+1] + A[idx+2])/3.0 can easily overflow!

You can read the formal proof by Minh Tran Dao here.

##### Solution:
```def solution(A):
min_idx = 0
min_value = 10001

for idx in xrange(0, len(A)-1):
if (A[idx] + A[idx+1])/2.0 < min_value:
min_idx = idx
min_value = (A[idx] + A[idx+1])/2.0
if idx < len(A)-2 and (A[idx] + A[idx+1] + A[idx+2])/3.0 < min_value:
min_idx = idx
min_value = (A[idx] + A[idx+1] + A[idx+2])/3.0

return min_idx
```

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.