Solution to Codility lesson2-exercise2 Permutation Check problem, link to Codility problem and complete solution at the end of the post.

**Definitions:**

**Codility Permutation definition:** A *permutation *of size N is a sequence containing each element from 1 to N once, and only once.

** Problem:**Define a function

*solution*with input

*A*, such that

*solution*returns

*1*if

*A*is a permutation and

*0*if it is not.

- Expected worst-case time complexity is
*O(N)*; - Expected worst-case space complexity is
*O(N)*, beyond input storage (not counting the storage required for input arguments).

**Elements of input arrays can be modified.**** **

### Analysis:

This one is very similar to the Frog River One, we’ll also count the first appearance of every element of the sequence

, but if we find a element of *A * that is greater than *N * or a duplicate element this means that A can’t be a permutation by the Codility definition.

10 11 12 13 14 15 16 17 18 |
for k in xrange(N): # If A has an element greater than N, A can't be a permutation from 1 to N if A[k] > N: return 0; # If it's the first time that A[k] appears count that, otherwise A can't be a permutation from 1 to N if count[A[k]] == 0: count[A[k]] = 1 else: return 0 |

If we visited all elements of *A *and didn’t find any repeated element or any greater than *N, *this means that we have a *permutation*, and we can return 1.

Since we have to visit all elements of *A* to guarantee that *A* is a *permutation *the total time complexity is *O(N)*.

For the space complexity, we’ll have *O(N)*, because of the *count* array, since its size depends on the value of *N*.

**Complete Solution:**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
# Name: PermCheck # Link: https://codility.com/demo/take-sample-test/perm_check/ def solution(A): N = len(A) # Counts appearance of elements of the sequence {1...N} count = [0]*(N + 1) for k in xrange(N): # If A has an element greater than N, A can't be a permutation from 1 to N if A[k] > N: return 0; # If it's the first time that A[k] appears count that, otherwise A can't be a permutation from 1 to N if count[A[k]] == 0: count[A[k]] = 1 else: return 0 return 1 |

*Time Complexity O(N)*

*Space Complexity O(N)*