Codility Demo Test Solution

Recently I came across a Codility demo task. I found it interesting enough to post here.

At first, I wanted to use a greedy algorithm, tracking the minimum positive integer so far. Take the following array: [1, 3, 6, 4, 1, 2]. Let’s iterate it. The first number is 1. So the minimum integer that is not in this array so far is 2. Then there is 3. So the minimum integer that is not in this array so far is still 2. Everything’s great until I finally encounter 2 in the end of this array. So how am I supposed to come up with an answer — 5 — with this approach? Well, I’m afraid it simply doesn’t work here. So it became obvious that I need to remember somehow all the encountered numbers.

What is the best way to spot them? The approach that comes to mind first is to have some pattern array, kinda sieve, the one that contains all the positive integers within a given interval. And it would be very handy if its keys would coincide with values. So with every integer I encounter in input array I find a corresponding key in a pattern array, and mark its value as, say, null:

$pattern = range(0, 100000);

foreach ($a as $value) {$pattern[$value] = null;}

After that all I need is to iterate it and find the first key with a non-null value. But before that I want to make sure that I won’t get 0 as an answer since it’s not a positive integer. So I unset the first element in my pattern array. And there is an edge case. What happens if I get all the integers within a given interval, [1, 100000]? The answer should be 100001. So I create a pattern array with the supremum equals to 100001:

function solution(array $a) {$pattern = range(0, 100001);

**foreach** ($a **as** $value) {  
    $pattern\[$value\] = **null**;  
}  

**unset**($pattern\[0\]);  

**for** ($i = 1; $i <= _count_($pattern); $i++) {  
    **if** (!_is\_null_($pattern\[$i\])) {  
        **return** $i;  
    }  
}  

}

Voilà!