codility-find-missing-element.php

<?php

/**
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)].
*/

function solution($a) {
    $missing = null;

    sort($a);

    $total = $a[count($a) - 1];
    $items = $a;

    function isMissingItem($a)
    {
        $supposed = $a[0] + (count($a) - 1);

        return $supposed != $a[count($a) - 1];
    }

    while ($missing == null) {

        $half = ceil($total / 2);

        $half_one = array_slice($items, 0, $half);
        $half_two = array_slice($items, $half);

        if (isMissingItem($half_one)) {
            $items = $half_one;
        } elseif (isMissingItem($half_two)) {
            $items = $half_two;
        }

        if ($half_one[count($half_one) - 1] + 1 != $half_two[0]) {
            $missing = $half_one[count($half_one) - 1] + 1;
            break;
        }

        $total = count($items);
    }
    
    return $missing;
}