08/25/14

# Codility ‘TieRopes’ Solution

##### Short Problem Definition:

Tie adjacent ropes to achieve the maximum number of ropes of length >= K.

TieRopes

##### Complexity:

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

expected worst-case space complexity is O(N)

##### Execution:

I am a bit skeptical about the correctness of my solution. It gets 100/100 through…

##### Solution:
```def solution(K, A):
cnt = 0
current = 0
for part in A:
current += part
if current >= K:
cnt +=1
current = 0

return cnt
```

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

08/15/14

# Codility ‘CountDistinctSlices’ Solution

##### Short Problem Definition:

Count the number of distinct slices (containing only unique numbers).

CountDistinctSlices

##### Complexity:

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

expected worst-case space complexity is O(M)

##### Execution:

Using the caterpillar method I expand the caterpillar to the right as long as a duplicate element is found. The right side has to retract as long as this duplicate element has been eliminated from the next slice. An observation showed that the number of sub-slices is equal to front-back+1.

##### Solution:
```def solution(M, A):
the_sum = 0
front = back = 0
seen = [False] * (M+1)
while (front < len(A) and back < len(A)):
while (front < len(A) and seen[A[front]] != True):
the_sum += (front-back+1)
seen[A[front]] = True
front += 1
else:
while front < len(A) and back < len(A) and A[back] != A[front]:
seen[A[back]] = False
back += 1

seen[A[back]] = False
back += 1

return min(the_sum, 1000000000)
```

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

08/14/14

# Codility ‘AbsDistinct’ Solution

##### Short Problem Definition:

Compute number of distinct absolute values of sorted array elements.

AbsDistinct

##### Complexity:

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

expected worst-case space complexity is O(N)

##### Execution:

Additional storage is allowed. Therefore a simple python solution will suffice.

##### Solution:
```def solution(A):
return len(set([abs(x) for x in A]))
```

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

08/13/14

# Codility ‘TreeHeight’ Solution

##### Short Problem Definition:

Compute the height of a binary link-tree.

TreeHeight

##### Complexity:

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

expected worst-case space complexity is O(N)

##### Execution:

The height of a tree is the maximal height +1 of its subtrees. In this specification a tree with just the root node has a height of 0.

##### Solution:
```'''
class Tree(object):
x = 0
l = None
r = None
'''

def getHeight(sub_T):
if sub_T == None:
return 0
return max(getHeight(sub_T.l), getHeight(sub_T.r))+1

def solution(T):
return max(getHeight(T.l), getHeight(T.r))
```

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

08/12/14

# Codility ‘MinAbsSumOfTwo’ Solution

##### Short Problem Definition:

Find the minimal absolute value of a sum of two elements.

MinAbsSumOfTwo

##### Complexity:

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

expected worst-case space complexity is O(1)

##### Execution:

Using the caterpillar method on a sorted list.

##### Solution:

C-style python

```def solution(A):
value = 2000000000
front_ptr = 0
back_ptr = len(A)-1
A.sort()

while front_ptr <= back_ptr: value = min(value, abs(A[front_ptr] + A[back_ptr])) if abs(A[front_ptr]) > abs(A[back_ptr]):
front_ptr += 1
else:
back_ptr -= 1

return value
```

Functional pythonesque:

```from itertools import *
def getAbsDiff(t):
return abs(t + t)

def solution(A):
A.sort(key=abs)
return getAbsDiff(min(chain(izip(A, A),izip(A,A[1:])), key = getAbsDiff))
```

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

08/11/14

# Codility ‘CommonPrimeDivisors’ Solution

##### Short Problem Definition:

Check whether two numbers have the same prime divisors.

CommonPrimeDivisors

##### Complexity:

expected worst-case time complexity is O(Z*log(max(A)+max(B))2);

expected worst-case space complexity is O(1)

##### Execution:

I will post an explaining image soon!

##### Solution:
```def gcd(p, q):
if q == 0:
return p
return gcd(q, p % q)

def hasSameFactors(p, q):
if p == q == 0:
return True

denom = gcd(p,q)

while (p != 1):
p_gcd = gcd(p,denom)
if p_gcd == 1:
break
p /= p_gcd
else:
while (q != 1):
q_gcd = gcd(q,denom)
if q_gcd == 1:
break
q /= q_gcd
else:
return True

return False

def solution(A, B):
if len(A) != len(B):
raise Exception("Invalid input")
cnt = 0
for idx in xrange(len(A)):
if A[idx] < 0 or B[idx] < 0:
raise Exception("Invalid value")
if hasSameFactors(A[idx], B[idx]):
cnt += 1

return cnt
```

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

08/10/14

# Codility ‘ChocolatesByNumbers’ Solution

##### Short Problem Definition:

There are N chocolates in a circle. Count the number of chocolates you will eat.

ChocolatesByNumbers

##### Complexity:

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

expected worst-case space complexity is O(1)

##### Execution:

N and M meet at their least common multiply. Dividing this LCM by M gets the number of steps(chocolates) that can be eaten.

##### Solution:
```def gcd(p, q):
if q == 0:
return p
return gcd(q, p % q)

def lcm(p,q):
return p * (q / gcd(p,q))

def solution(N, M):
return lcm(N,M)/M
```

```def naive(N,M):
eaten = [False] * N
at = 0
cnt = 0
while eaten[at] != True:
eaten[at] = True
at = (at + M) % N
cnt += 1

return cnt
```

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

08/9/14

##### Short Problem Definition:

Find the index S such that the leaders of the sequences A, A, …, A[S] and A[S + 1], A[S + 2], …, A[N – 1] are the same.

##### Complexity:

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

expected worst-case space complexity is O(N)

##### Execution:

Get the leader as in the training material. Afterwards check every position if both sides have enough leader occurrences.

##### Solution:
```def solution(A):
candidate_ele = ''
candidate_cnt = 0

for value in A:
if candidate_ele == '':
candidate_ele = value
candidate_cnt = 1
else:
if value != candidate_ele:
candidate_cnt -= 1
if candidate_cnt == 0:
candidate_ele = ''
else:
candidate_cnt += 1

if candidate_cnt == 0:
return 0

cnt = 0
last_idx = 0

for idx, value in enumerate(A):
if value == candidate_ele:
cnt += 1
last_idx = idx

if cnt < len(A)//2:
return 0

equi_cnt = 0
cnt_to_the_left = 0
for idx, value in enumerate(A):
if value == candidate_ele:
cnt_to_the_left +=1
if cnt_to_the_left > (idx + 1)//2 and \
cnt - cnt_to_the_left > (len(A) - idx - 1) //2:
equi_cnt += 1

return equi_cnt
```

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

08/8/14

# Codility ‘Dominator’ Solution

##### Short Problem Definition:

Find an index of an array such that its value occurs at more than half of indices in the array.

Dominator

##### Complexity:

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

expected worst-case space complexity is O(1)

##### Execution:

As explained in the training material…

##### Solution:
```def solution(A):
candidate_ele = ''
candidate_cnt = 0

for value in A:
if candidate_ele == '':
candidate_ele = value
candidate_cnt = 1
else:
if value != candidate_ele:
candidate_cnt -= 1
if candidate_cnt == 0:
candidate_ele = ''
else:
candidate_cnt += 1

if candidate_cnt == 0:
return -1

cnt = 0
last_idx = 0

for idx, value in enumerate(A):
if value == candidate_ele:
cnt += 1
last_idx = idx

if cnt > len(A)//2:
return last_idx

return -1
```

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

08/7/14

# Codility ‘Triangle’ Solution

##### Short Problem Definition:

Determine whether a triangle can be built from a given set of edges.

Triangle

##### Complexity:

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

expected worst-case space complexity is O(N)

##### Execution:

By sorting the array, we have guaranteed that P+R > Q and Q+R > P (because R is always the biggest). Now what remains, is the proof that P+Q > R, that can be found out by traversing the array. The chance to find such a combination is with three adjacent values as they provide the highest P and Q.

##### Solution:
```def solution(A):
if len(A) < 3:
raise Exception("invalid input")

A.sort()

for i in xrange(len(A)-2):
if A[i] + A[i+1] > A[i+2]:
return 1

return 0
```

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