# Codility - Missing Integer

Solution to Codility lesson2-exercise3 Missing Integer problem, link to Codility problem and complete solution at the end of the post.

Definitions:
$\mathbf{A} = \{x \in \mathbb{Z}\ |-2,147,483,647 \leq x \leq 2,147,483,647 \land |A| = N \},\mathbf{A}\, is\, a\, multiset.$
$\{N \in \mathbb{N}\ |\ 1 \leq N \leq 100,000\}$

Problem:
Define a function solution with input A, such that solution returns the minimal positive integer (greater than 0) that does not belongs to A.

• 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:

First we count every element of A that belongs to the sequence $\{1,...,N\}$.

The time complexity for counting all elements of an array is O(N), since you have to travel through all elements of the array.
Having the count array, we'll go through the count array and the first element with count 0, it's the solution of this problem.

If we have every element of the count array, this means that  is the sequence $\{1,...,N\}$ and the minimal missing integer is N + 1.
The count array has N + 1 elements, the worst case will be if A is the sequence $\{1,...,N\}$ and we have to visit every element of the count array, giving us a time complexity of O(N). This will give us a total time complexity of O(N) + O(N) which gives us a final time complexity of O(N).
For the space complexity we have O(N) because the count array has it's sizes depending on the size of the input.

### Complete Solution: Missing Element Python # Name: MissingInteger # Link: https://codility.com/demo/take-sample-test/missing_integer/ def solution(A): N = len(A) count = [0]*(N + 1) # Counts all elements of A tha belongs to sequence {1, ..., N} for k in xrange(N): if N >= A[k] > 0: count[A[k]] += 1 # Searches for the lesser integer that not belongs to A for k in xrange(1, N + 1): if count[k] == 0: return k # If A has all elements from 1 to N, N + 1 is the minimal integer return N + 1 1234567891011121314151617181920 # Name: MissingInteger# Link: https://codility.com/demo/take-sample-test/missing_integer/  def solution(A):    N = len(A)    count = [0]*(N + 1)        # Counts all elements of A tha belongs to sequence {1, ..., N}    for k in xrange(N): if N >= A[k] > 0:            count[A[k]] += 1        # Searches for the lesser integer that not belongs to A     for k in xrange(1, N + 1):        if count[k] == 0:            return k        # If A has all elements from 1 to N, N + 1 is the minimal integer    return N + 1

Time Complexity O(N)
Space Complexity O(N)