为什么 Perm-Missing-Elem Codility 测试为我的代码返回 66/100 结果，并显示“结果类型无效，需要 int”？

Question

注意：请勿发布您自己的“100/100 工作”代码片段作为本文的答案。这不是问题所要问的。

---

我开始使用 Codility 并遇到了这个问题：

给出一个由 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 是 [0..100,000] 范围内的整数；
• A 的元素都是不同的；
• 数组 A 的每个元素都是 [1..(N + 1)] 范围内的整数。

复杂性：

• 预计最坏情况时间复杂度为O(N)；
• 预计最坏情况的空间复杂度为 O(1)，超出输入存储（不计算输入参数所需的存储）。

我已经在 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
tested program terminated unexpectedly
stdout:
Invalid result type, int expected.

我在本地测试了 100.000 个元素的数组，它运行没有任何问题。那么，我的代码似乎有什么问题以及 Codility 使用了什么样的测试用例来返回

结果类型无效，应为 int

Answer 1

其他人已经回答了最初的问题，但我想提供对问题的更多见解，并分享一个快速的 C++ 替代解决方案。

当然，解决方案是基于古老的算术技巧，将一大组连续数字相加，这一点众所周知是卡尔·弗里德里希·高斯在他还是个小男孩时发现的。

由于 N>65,536 的乘法超过 32 位精度，OP 遇到了整数溢出问题。对于给定的 N = [0..100,000] 范围，这里有一个小技巧可以避免这种情况。 当计算 [1..N+1] 中的数字的所有整数之和（高斯和）时，我们减去 (N+2)/2 的偏移量，使其为零和（或最多为“偏移量”）情况 N 为奇数）。同样，我们也从数组中的所有值中减去这个偏移量。通过这种方式，我们将要添加的数字范围调整为最多 [-50,000...+50,000]。在最坏的情况下，即如果所有正（或负）范围数都按顺序排列，则最大中间和永远不会超过 31 位，因此不会发生溢出。对于交错的正数和负数，中间和会更小。

从高斯和中减去数组和后，我们再次通过添加偏移量来纠正以找到丢失的数组元素。

这是 C++ 代码（在 codility 测试中得分为 100%）：

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;
}

Answer 2

执行乘法时，您似乎已经达到了 PHP 变量可以容纳的最大值。我不确定 PHP 是否允许您使用位，但是使用类似于 Java 的

BitSet

类的东西可以轻松解决这个问题。

解决方案的要点是，因为我们知道数字将在 1 和 n 之间，所以在索引为输入数组元素的变量中将这些位设置为 1。现在有另一个变量，它的所有位都设置在位置 1 到 n（包括 n）中。对这些变量进行 XOR 将给出丢失数字的位置。

这里是实现上述逻辑的Java代码（也是Codility上的100/100）

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;
}