# Codility - Permutation Check

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

Definitions:
$\mathbf{A} = \{x \in \mathbb{N}\ | 1 \leq x \leq 1,000,000,000 \land |A| = N \},\mathbf{A}\, is\, a\, multiset.$
$\{N \in \mathbb{N}\ |\ 1 \leq N \leq 100,000\}$
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 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 $\{1,..,N\}$, but if we find a element of  that is greater than or a duplicate element this means that A can't be a permutation by the Codility definition.

If we visited all elements of 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: Permutation Check Python # 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 1234567891011121314151617181920 # 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)