05/28/14

# Codility ‘PermMissingElem’ Solution

##### Short Problem Definition:

Find the missing element in a given permutation.

PermMissingElem

##### Complexity:

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

expected worst-case space complexity is O(1)

##### Execution:

Sum all elements that should be in the list and sum all elements that actually are in the list. The sum is 0 based, so +1 is required. The first solution using the + operator can cause int overflow in not-python languages. Therefore the use of a binary XOR is adequate.

##### Solution:
```def solution(A):
should_be = len(A) # you never see N+1 in the iteration
sum_is = 0

for idx in xrange(len(A)):
sum_is += A[idx]
should_be += idx+1

return should_be - sum_is +1
```

```def solution(A):
missing_element = len(A)+1

for idx,value in enumerate(A):
missing_element = missing_element ^ value ^ (idx+1)

return missing_element
```

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

05/22/14

# Codility ‘PermCheck’ Solution

##### Short Problem Definition:

Check whether array N is a permutation.

PermCheck

##### Complexity:

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

expected worst-case space complexity is O(N)

##### Execution:

Mark elements as seen in a boolean array. Elements seen twice or out of bounds of the size indicate that the list is no permutation. The check if the boolean array only contains true elements is not required. This solution only works with permutations starting from 1.

##### Solution:
```def solution(A):
seen = [False] * len(A)

for value in A:
if 0 <= value > len(A):
return 0
if seen[value-1] == True:
return 0
seen[value-1] = True

return 1
```

```int solution(vector<int> &A) {
// the use of a auto_ptr would be better, but it does not work with arrays
// use of boost::scoped_array seems like an overkill
bool * seen = new bool[A.size()];

for (unsigned int i=0; i< A.size(); i++){
seen[i] = false;
}

for (unsigned int i=0; i< A.size(); i++){
if (!(0 < A[i] && A[i] <=A.size() && seen[A[i]-1] == false)){
delete[] seen;
return 0;
} else {
seen[A[i]-1] = true;
}
}

delete[] seen;
return 1;
}
```

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

05/20/14

# Codility ‘FrogRiverOne’ Solution

##### Short Problem Definition:

Find the earliest time when a frog can jump to the other side of a river.

FrogRiverOne

##### Complexity:

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

expected worst-case space complexity is O(X)

##### Execution:

Mark seen elements as such in a boolean array. I do not like the idea of returning the first second as 0. But specifications are specifications 🙂

##### Solution:
```def solution(X, A):
passable = [False] * X
uncovered = X

for idx in xrange(len(A)):
if A[idx] <= 0 or A[idx] > X:
raise Exception("Invalid value", A[idx])
if passable[A[idx]-1] == False:
passable[A[idx]-1] = True
uncovered -= 1
if uncovered == 0:
return idx

return -1
```

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