What is wrong with this solution? (Perm-Missing-Elem codility test)

Question

I have started playing with codility and came across this problem:

A zero-indexed 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:

int solution(int A[], int N); 

that, given a zero-indexed 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.

Assume that:

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

Complexity:

    expected worst-case time complexity is O(N);
    expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

I have submitted the following solution (in PHP):

function solution($A) {
    $nr = count($A);
    $totalSum = (($nr+1)*($nr+2))/2;
    $arrSum = array_sum($A);
    return ($totalSum-$arrSum);
}

which gave me a score of 66 of 100, because it was failing the test involving large arrays: "large_range range sequence, length = ~100,000" with the result: RUNTIME ERROR tested program terminated unexpectedly stdout: Invalid result type, int expected.

I tested locally with an array of 100.000 elements, and it worked without any problems. So, what seems to be the problem with my code and what kind of test cases did codility use to return "Invalid result type, int expected"?

Answer 1

A 100/100 php solution for PermMissingElem:

function solution($A) {   
    $N   = count($A);
    $sum = ($N + 2) * ($N + 1) / 2;
    for($i = 0; $i < $N; $i++){
        $sum -= $A[$i];
    }
    return intval($sum);
}

Answer 2

Others have already answered the original question, but I thought to provide some more insight into the problem and share an alternative solution in C++ that is fast.

The solution, of course, is based on the old arithmetic trick to add up a large set of contiguous numbers, famously attributed to Carl Friedrich Gauss who discovered it when he was a young boy.

The OP ran into a problem with integer overflow due to the multiplication exceeding 32-bit precision for N>65,536. Here's a little trick to avoid that for the given range of N = [0..100,000]. When computing the sum of all ints (Gauss sum) for the numbers in [1..N+1] we subtract an offset of (N+2)/2 to make it a zero-sum (or at most "offset" in case N is odd). Similarly we also subtract this offset from all the values in the array. This way we shift the range of numbers to be added to at most [-50,000...+50,000]. In the worst case, i.e. if all positive (or negative) range numbers are in sequence, the largest intermediate sum never exceeds 31 bits, so no overflow will occur. For interleaved positive and negative numbers the intermediate sum will be even smaller.

After subtracting the array sum from the Gauss sum we again correct by adding back the offset to find the missing array element.

Here's the code in C++ (it scored 100% in the codility test):

int solution(vector<int> &A) {
    int N;
    int sum;
    int gauss;              // sum of all ints in [1..N+1] using Gauss' trick
    int offset;             // subtract offset from all numbers to make it a zero-sum
    int num_x;


    N = int(A.size());      // convert from size_t to int

    sum = 0;
    offset = (N+2) >> 1;        // make range symmetric between [-N/2..N/2] to avoid integer overflow in Gauss sum for large N

    // "gauss" should nominally be a zero sum, but if N is odd then N/2 is truncated 
    // and offset is off by 1/2 for each of the N elements. This formula compensates for that.
    gauss = (N & 1) * offset;

    for (int i = 0; i < N; i++) {
        sum += (A[i] - offset);     // this is the O(n) part of summing all elements in the array
    }

    num_x = gauss - sum + offset;   // find the missing number

    return num_x;
}