07/31/14

# Codility ‘Peaks’ Solution

##### Short Problem Definition:

A non-empty zero-indexed array A consisting of N integers is given. A peak is an array element which is larger than its neighbors.

Peaks

##### Complexity:

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

expected worst-case space complexity is O(N)

##### Execution:

I first compute all peaks. Because each block must contain a peak I start from the end and try to find a integral divisor sized block. If each block contains a peak I return the size.

##### Solution:
```
def solution(A):
peaks = []

for idx in xrange(1, len(A)-1):
if A[idx-1] < A[idx] > A[idx+1]:
peaks.append(idx)

if len(peaks) == 0:
return 0

for size in xrange(len(peaks), 0, -1):
if len(A) % size == 0:
block_size = len(A) // size
found = [False] * size
found_cnt = 0
for peak in peaks:
block_nr = peak//block_size
if found[block_nr] == False:
found[block_nr] = True
found_cnt += 1

if found_cnt == size:
return size

return 0

```

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

07/29/14

# Codility ‘MinPerimeterRectangle’ Solution

##### Short Problem Definition:

Find the minimal perimeter of any rectangle whose area equals N.

MinPerimeterRectangle

##### Complexity:

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

expected worst-case space complexity is O(1).

##### Execution:

Trivial search for the largest prime.

##### Solution:
```import math
def solution(N):
if N <= 0:
return 0

for i in xrange(int(math.sqrt(N)), 0, -1):
if N % i == 0:
return 2*(i+N/i)

raise Exception("should never reach here!")
```

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

07/28/14

# Codility ‘Count Factors’ Solution

##### Short Problem Definition:

Count factors of given number N.

CountFactors

##### Complexity:

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

expected worst-case space complexity is O(1).

##### Execution:

This example can be found in the lesson document.

##### Solution:
```def solution(N):
cnt = 0
i = 1
while ( i * i <= N):
if (N % i == 0):
if i * i == N:
cnt += 1
else:
cnt += 2
i += 1
return cnt
```

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

07/25/14

# Codility ‘Nesting’ Solution

##### Short Problem Definition:

Determine whether given string of parentheses is properly nested.

Nesting

##### Complexity:

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

expected worst-case space complexity is O(1)

##### Execution:

Because there is only one type of brackets, the problem is easier than Brackets. Just check if there is always a opening bracket before a closing one.

##### Solution:
```def solution(S):
leftBrackets = 0

for symbol in S:
if symbol == '(':
leftBrackets += 1
else:
if leftBrackets == 0:
return 0
leftBrackets -= 1

if leftBrackets != 0:
return 0

return 1
```

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

07/23/14

# Codility ‘FrogJmp’ Solution

##### Short Problem Definition:

Count minimal number of jumps from position X to Y.

FrogJmp

##### Complexity:

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

expected worst-case space complexity is O(1).

##### Execution:

Do not use float division if possible!

##### Solution:
```def solution(X, Y, D):
if Y < X or D <= 0:
raise Exception("Invalid arguments")

if (Y- X) % D == 0:
return (Y- X) // D
else:
return ((Y- X) // D) + 1
```

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

07/22/14

# Codility ‘Tape Equilibrium’ Solution

##### Short Problem Definition:

Minimize the value |(A + … + A[P-1]) – (A[P] + … + A[N-1])|.

TapeEquilibrium

##### Complexity:

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

expected worst-case space complexity is O(N)

##### Execution:

In the first run I compute the left part up to the point i and the overall sum last. Then I compute the minimal difference between 0..i and i+1..n.

##### Solution:
```import sys

def solution(A):
#1st pass
parts =  * len(A)
parts = A

for idx in xrange(1, len(A)):
parts[idx] = A[idx] + parts[idx-1]

#2nd pass
solution = sys.maxint
for idx in xrange(0, len(parts)-1):
solution = min(solution,abs(parts[-1] - 2 * parts[idx]));

return solution
```

```#include <algorithm>
#include <climits>

int solution(vector<int> &A) {
unsigned int size = A.size();

vector<long long> parts;
parts.reserve(size+1);

long long last = 0;

for (unsigned int i=0; i<size-1; i++){
if (i == 0){
parts.push_back(A[i]);
} else {
parts.push_back(A[i]+parts[i-1]);
}
if (i==size-2){
last = parts[i]+ A[i+1];
}
}

long long solution = LLONG_MAX;

for(unsigned int i=0; i<parts.size(); i++){
solution = min(solution,abs(last - 2 * parts[i]));
}

return solution;
}
```

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

07/18/14

# Codility ‘Fish’ Solution

##### Short Problem Definition:

N voracious fish are moving along a river. Calculate how many fish are alive.

Fish

##### Complexity:

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

expected worst-case space complexity is O(N)

##### Execution:

Put all downstream swimming fishes on a stack. Any upstream swimming fish has to fight(eat) all fishes on the stack. If there is no fish on the stack, the fish survives. If the stack has some downstream fishes at the end, they also survive.

##### Solution:
```def solution(A, B):
survivals = 0
stack = []

for idx in xrange(len(A)):
if B[idx] == 0:
while len(stack) != 0:
if stack[-1] > A[idx]:
break
else:
stack.pop()

else:
survivals += 1
else:
stack.append(A[idx])

survivals += len(stack)

return survivals
```

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

07/10/14

# Codility ‘Brackets’ Solution

##### Short Problem Definition:

Determine whether a given string of parentheses is properly nested.

Brackets

##### Complexity:

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

expected worst-case space complexity is O(N)

##### Execution:

Put every opening bracket on a stack. If a closing bracket is not the same as the top stack bracket, the string is not properly nested.

##### Solution:
```def isValidPair(left, right):
if left == '(' and right == ')':
return True
if left == '[' and right == ']':
return True
if left == '{' and right == '}':
return True
return False

def solution(S):
stack = []

for symbol in S:
if symbol == '[' or symbol == '{' or symbol == '(':
stack.append(symbol)
else:
if len(stack) == 0:
return 0
last = stack.pop()
if not isValidPair(last, symbol):
return 0

if len(stack) != 0:
return 0

return 1
```

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