Codility

MissingInteger.php

<?php
/*
This is a demo task.

Write a function that, given an array A of n integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.
Given A = [1, 2, 3], the function should return 4.
Given A = [-1, -3], the function should return 1.

Assume that:
• n is an integer within the range [1 … 100,000];
• each element of array A is an integer within the range [-1,000,000 … 1,000,000].

Complexity:
• expected worst-case time complexity is O(n);
• expected worst-case space complexity is O(n) (not counting the storage required for input arguments).

*/

function solution($A) {
    if (!in_array(1, $A)) {
        return 1;
    }
    
    $A = array_filter($A, function($a){
       return $a > 0; 
    });
    
    sort($A);
    $n = count($A);
    for ($i = 1; $i < $n; $i++) {
        if ($A[$i] - $A[$i - 1] > 1) {
            return $A[$i - 1] + 1;
        }
    }
    
    return $A[$n-1]+1;
}