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 = [0] * 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.