algorithm - 证明 XOR 不适用于查找丢失的数字(面试问题)？

Question

面试问题:你得到了一个包含大约 10 亿个唯一数字的文件，每个数字都是一个 32 位数字。找到一个不在文件中的数字。

当我接近这个问题时，我尝试了几个 3 位和 4 位数字的例子。对于我尝试过的示例，我发现当我对数字集进行异或运算时，我得到了正确的答案:

a = [0,1,2] # missing 3
b = [1,2,3] # missing 0
c = [0,1,2,3,4,5,6] # missing 7
d = [0,1,2,3,5,6,7] # missing 4

functools.reduce((lambda x, y: x^y), a) # returns 3
functools.reduce((lambda x, y: x^y), b) # returns 0
functools.reduce((lambda x, y: x^y), c) # returns 7
functools.reduce((lambda x, y: x^y), d) # returns 4

但是，当我将其编码并提交时，它未能通过测试用例。

我的问题是:在面试环境中，我如何确定或排除这样的方法不是可行的解决方案？

Answer 1

在您的所有示例中，数组恰好缺少一个数字。这就是 XOR 起作用的原因。尽量不要使用相同的属性进行测试。

对于问题本身，可以通过取每一位的少数来构造一个数。

编辑

为什么 XOR 对您的示例有效:

当您对从 0 到 2^n - 1 的所有数字进行异或运算时，结果为 0(每个位正好有 2^(n-1) 个“1”)。因此，如果您取出一个数字并与其余所有数字进行异或，结果就是您取出的数字，因为该数字与其余所有数字的异或结果需要为 0。