这个解决方案有什么问题？(Perm-Missing-Elem codility test)

Question

我已经开始玩鳕鱼并遇到了这个问题:

给出了由N个不同整数组成的零索引数组A. 该数组包含[1 ..(N + 1)]范围内的整数,这意味着只缺少一个元素.

你的目标是找到缺少的元素.

写一个函数:

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

在给定零索引数组A的情况下,返回缺少元素的值.

例如,给定数组A,使得:

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

函数应该返回4,因为它是缺少的元素.

假使,假设:

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

复杂:

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

我已经提交了以下解决方案(在PHP中):

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

这给了我得分66的100,因为它没有涉及大数组的测试:"large_range范围序列,长度= ~100,000",结果:RUNTIME ERROR测试程序意外终止stdout:结果类型无效,int预期.

我在本地测试了100,000个元素的数组,它没有任何问题.那么,我的代码似乎是什么问题以及什么样的测试用例使用codility来返回"无效的结果类型,int expected"？

Answer 1

PermMissingElem的100/100 php解决方案:

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