Problem

An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

    function solution($A);

that, given an array A, returns the value of the missing element.

For example, given array A such that:

  A[0] = 2
  A[1] = 3
  A[2] = 1
  A[3] = 5

the function should return 4, as it is the missing element.

Write an efficient algorithm for the following assumptions:

    •         N is an integer within the range [0..100,000];
    •         the elements of A are all distinct;
    •         each element of array A is an integer within the range [1..(N + 1)].

Note:

The values in the array start from 1 to N + 1. They are simply not arranged in ascending order. In the illustration array, of the problem, there are 4 elements, and when arranged in ascending order, they become 1, 2, 3, 5. It can clearly be seen from this ascending order, that 4 is missing.

It can be very cumbersome to solve this problem, the brute-force (direct) way. The best way to do it is to sort the array, and then scan it for the missing element. This will give O(Nxlog(N)) time complexity at app.codility.com/programmers .

Solution

app.codility.com/programmers allows the candidate to use the predefined sort() function in PHP. The array has this sort() method. The following program offers the solution (read the code and comments):

<?php
    //sort using PHP array sort, then look for the missing element from the beginning
    function solution($A) {
        $N = count($A);

        sort($A);  //sort method from the array data structure

        $ctr = 1;  //counter
        for ($i=0; $i < $N; $i++){
            if ($ctr != $A[$i]) 
                return $ctr;    //missing element
            ++$ctr;
        }

        return $ctr;   //element is missed at end of list
    }

    $B = [2, 3, 1, 5];
    $miss = solution($B);
    echo $miss . "\n";
?>

The value of ctr is incremented at the end of the for-loop's body. It is synchronized with the sorted elements. In the for-loop scan, when it is not equal to a sorted element, then its value is the missing element; otherwise the element is missed at the end of list.

The example test has been used here. On submission at app.codility.com/programmers, at least 8 test cases not shown here will assess your solution. Remember that at app.codility.com/programmers, the PHP calling function is not submitted.

Conclusion

To solve a similar problem, efficiently, sort the array, and then scan for the missing element.

The reader should register at app.codility.com/programmers and be testing his/her code, in order to gain confidence.