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

**Definitions:**

** 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

.

9 10 11 12 |
# 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 |

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.

14 15 16 17 |
# Searches for the lesser integer that not belongs to A for k in xrange(1, N + 1): if count[k] == 0: return k |

If we have every element of the count array, this means that *A * is the sequence

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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
# 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)*