Why does the Perm-Missing-Elem Codility test return a 66/100 result for my code, and show me "Invalid result type, int expected"?

NOTICE: Do NOT post your own "100/100 working" code snippets as answers to this post. That is NOT what the question is asking for.

I have started using 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

Solution

It looks like you are hitting the maximum value a PHP variable can hold when you are performing the multiplication. I am not sure if PHP allows you to work with bits, but this problem can be solved easily using something similar to Java's BitSet class.

The gist of the solution is, since we know that the numbers will be between 1 and n, set those bits to 1 in a variable whose indices are the elements of the input array. Now have another variable which has all the bits set in positions, 1 through and including n. Doing an XOR of these variables will give you the position of the missing number.

Here is Java code that implements the above logic (also a 100/100 on Codility)

public int solution(int[] A) {
    long result = 0L;

    BitSet all_elements = new BitSet();
    BitSet given_elements = new BitSet();
    
    for (int i = 0; i < A.length; i++) {
        given_elements.set((int) A[i]);
    }
    
    for (int i = 1; i <= A.length + 1; i++) {
        all_elements.set(i);
    }
    
    all_elements.xor(given_elements);

    for (int i = 0; i < all_elements.length(); ++i) {
        if(all_elements.get(i)) {
            result = i;
            break;
        }
    }

    return (int)result;
}