生成一个不在 40 亿给定整数之中的整数

Question

我收到了这样一个面试问题：

给定一个包含 40 亿个整数的输入文件，提供一种算法来生成文件中未包含的整数。假设您有 1 GB 内存。跟进如果您只有 10 MB 内存您会做什么。

我的分析：

文件大小为4×10⁹×4字节=16GB。

我们可以进行外部排序，从而让我们知道整数的范围。

我的问题是检测排序大整数集中丢失的整数的最佳方法是什么？

我的理解（阅读所有答案后）：

假设我们谈论的是 32 位整数，则有 2³² = 4*10⁹ 个不同的整数。

情况 1：我们有 1 GB = 1 * 10⁹ * 8 位 = 80 亿位内存。

解决方案：

如果我们用一位代表一个不同的整数，就足够了。我们不需要排序。

实现：

int radix = 8;
byte[] bitfield = new byte[0xffffffff/radix];
void F() throws FileNotFoundException{
    Scanner in = new Scanner(new FileReader("a.txt"));
    while(in.hasNextInt()){
        int n = in.nextInt();
        bitfield[n/radix] |= (1 << (n%radix));
    }

    for(int i = 0; i< bitfield.lenght; i++){
        for(int j =0; j<radix; j++){
            if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);
        }
    }
}

情况 2：10MB 内存 = 10 * 10⁶ * 8 位 = 8000 万位

解决方案：

对于所有可能的 16 位前缀，有 2¹⁶ 个 整数 = 65536，我们需要 2¹⁶ * 4 * 8 = 200 万位。我们需要构建 65536 个存储桶。对于每个桶，我们需要 4 个字节来保存所有可能性，因为最坏的情况是所有 40 亿个整数都属于同一个桶。

1. 通过第一次遍历文件构建每个存储桶的计数器。
2. 扫描桶，找到第一个命中数小于 65536 的桶。
3. 构建新的存储桶，其高 16 位前缀是我们在步骤 2 中找到的 通过文件的第二遍
4. 扫描步骤3中构建的桶，找到第一个没有的桶 取得成功。

该代码与上面的代码非常相似。

结论： 我们通过增加文件传递来减少内存。

---

^{对那些迟到的人的澄清：所提出的问题并没有说文件中不包含确切的一个整数 - 至少大多数人不是这样解释它的。不过，评论线程中的许多评论都是关于任务的这种变化。不幸的是，将其引入评论线程的评论后来被其作者删除，所以现在看来​​，对它的孤立回复只是误解了一切。这很令人困惑，抱歉。}

Answer 1

假设“整数”表示 32 位：对于所有可能的 16 位，10 MB 的空间足以让您计算输入文件中具有任何给定 16 位前缀的数字有多少个位前缀一次通过输入文件。至少其中一个桶的撞击次数少于 2¹⁶ 次。进行第二遍以查找该存储桶中哪些可能的数字已被使用。

如果它意味着超过 32 位，但仍具有有限大小：按照上述操作，忽略所有恰好落在（有符号或无符号；您的选择）32 位范围之外的输入数字。

如果“整数”表示数学整数：通读一次输入并跟踪您见过的最长数字的最大数字长度。完成后，输出最大加一一个多一位的随机数。 （文件中的一个数字可能是一个大数，需要超过 10 MB 才能准确表示，但如果输入是一个文件，那么您至少可以表示适合的任何内容的长度它）。

Answer 2

统计信息算法使用比确定性方法更少的遍数来解决这个问题。

如果允许非常大的整数，那么就可以在 O(1) 时间内生成一个可能唯一的数字。像 GUID 这样的伪随机 128 位整数只会与现有的 40 亿个中的一个发生冲突集合中的整数不到每 640 亿个案例中的一个。

如果整数限制为 32 位，则可以使用远小于 10 MB 的空间在一次传递中生成一个可能唯一的数字。伪随机 32 位整数与 40 亿个现有整数之一发生冲突的几率约为 93% (4e9 / 2^32)。 1000 个伪随机整数全部发生碰撞的几率小于 120,000 亿亿分之一（一次碰撞的几率 ^ 1000）。因此，如果一个程序维护一个包含 1000 个伪随机候选的数据结构，并迭代已知的整数，消除候选中的匹配项，那么几乎肯定会找到至少一个不在文件中的整数。

Answer 3

Jon Bentley“第 1 栏：破解牡蛎”中对此问题进行了详细讨论< em>编程珍珠 Addison-Wesley pp.3-10

Bentley讨论了几种方法，包括外部排序、使用多个外部文件的合并排序等，但最好的方法Bentley 建议使用位字段的单遍算法，他幽默地将其称为“Wonder Sort”:)
谈到这个问题，40 亿个数字可以用以下形式表示：

4 billion bits = (4000000000 / 8) bytes = about 0.466 GB

实现位集的代码很简单：（取自 解决方案页面 )

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];

void set(int i) {        a[i>>SHIFT] |=  (1<<(i & MASK)); }
void clr(int i) {        a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int  test(int i){ return a[i>>SHIFT] &   (1<<(i & MASK)); }

Bentley 的算法对文件进行单次传递，设置数组中的适当位，然后使用上面的 test 宏可以找到丢失的号码。

如果可用内存小于 0.466 GB，Bentley 建议使用 k-pass 算法，该算法根据可用内存将输入划分为多个范围。举一个非常简单的例子，如果只有1个字节（即处理8个数字的内存）可用，并且范围是从0到31，我们将其分为0到7、8-15、16-22等范围并在每次 32/8 = 4 遍中处理这个范围。

HTH。

Answer 4

由于问题没有指定我们必须找到文件中没有的最小可能数字，因此我们可以生成一个比输入文件本身长的数字。 :)

Answer 5

对于 1 GB RAM 变体，您可以使用位向量。您需要分配 40 亿位 == 500 MB 字节数组。对于从输入中读取的每个数字，将相应的位设置为“1”。完成后，迭代这些位，找到第一个仍为“0”的位。它的索引就是答案。

Answer 6

如果它们是 32 位整数（可能是从接近 2³² 的约 40 亿个数字中选择的），则您的 40 亿个数字列表将最多占据可能整数的 93% (4 * 10⁹ / (2³²) )。因此，如果您创建一个 2³² 位的位数组，每个位都初始化为零（这将占用 2²⁹ 字节 ~ 500 MB RAM；记住一个字节 = 2³ 位 = 8 位），读取整数列表，并为每个 int 设置相应的位数组元素（从 0 到 1）；然后读取您的位数组并返回第一个仍为 0 的位

。如果您的 RAM 较少（~10 MB），则需要稍微修改此解决方案。 10 MB ~ 83886080 位仍然足以为 0 到 83886079 之间的所有数字创建位数组。因此您可以通读整数列表；并且仅在位数组中记录 0 到 83886079 之间的 #。如果数字是随机分布的；具有压倒性的概率（大约相差 100% 10^-2592069）你会发现一个丢失的int）。事实上，如果您只选择数字 1 到 2048（只有 256 字节的 RAM），您仍然会发现丢失的数字占绝大多数（99.99999999999999999999999999999999999999999999999999999999999995%）。

但我们假设数字不是大约 40 亿；您有类似 2³² - 1 个数字和小于 10 MB 的 RAM；所以任何小范围的整数只有很小的可能性不包含该数字。

如果保证列表中的每个 int 都是唯一的，则可以将数字相加，然后将缺少一个 # 的总和减去总和 (½)(2³²)(2³² - 1) = 9223372034707292160 找到丢失的 int。但是，如果 int 出现两次，则此方法将失败。

然而，你总是可以分而治之。一种简单的方法是读取数组并计算前半部分（0 到 2³¹-1）和后半部分（2³¹-1）的数字数量。 >, 2³²)。然后选择数字较少的范围，并重复将该范围一分为二。 （假设 (2³¹, 2³²) 中少了两个数字，那么您的下一次搜索将计算范围 (2³¹) 内的数字>, 3*2³⁰-1), (3*2³⁰, 2³²)，直到找到零的范围。应该需要 O(lg N) ~ 32 次读取数组。

我们在每个步骤中只使用两个整数（或者大约 8 字节的 RAM 和 4 字节（32 位）。 ) 更好的方法是分成 sqrt(2³²) = 2¹⁶ = 65536 个 bin，每个 bin 中有 65536 个数字。每个 bin 需要 4 个字节来存储其计数，因此您需要 2¹⁸ 字节 = 256 kB，因此 bin 0 为 (0 到 65535=2¹⁶-1)。 ，bin 1 为 (2¹⁶=65536 到 2*2¹⁶-1=131071)，bin 2是 (2*2¹⁶=131072 到 3*2¹⁶-1=196607)

import numpy as np
nums_in_bin = np.zeros(65536, dtype=np.uint32)
for N in four_billion_int_array:
    nums_in_bin[N // 65536] += 1
for bin_num, bin_count in enumerate(nums_in_bin):
    if bin_count < 65536:
        break # we have found an incomplete bin with missing ints (bin_num)

。 ; 并计算 2¹⁶ 每个 bin 中有多少个整数，并找到不包含所有 65536 个数字的 incomplete_bin。然后你再读一遍这个40亿的整数列表；但这次只注意整数何时在该范围内；当你找到它们时稍微翻转一下。

del nums_in_bin # allow gc to free old 256kB array
from bitarray import bitarray
my_bit_array = bitarray(65536) # 32 kB
my_bit_array.setall(0)
for N in four_billion_int_array:
    if N // 65536 == bin_num:
        my_bit_array[N % 65536] = 1
for i, bit in enumerate(my_bit_array):
    if not bit:
        print bin_num*65536 + i
        break

Answer 7

为什么要把事情搞得这么复杂呢？您要求提供文件中不存在的整数吗？

根据指定的规则，您唯一需要存储的是迄今为止在文件中遇到的最大整数。读取整个文件后，返回比该值大 1 的数字。

不存在命中 maxint 或其他任何问题的风险，因为根据规则，对于整数的大小或算法返回的数字没有限制。

Answer 8

这可以使用二分搜索的变体在很小的空间内解决。

1. 从允许的数字范围开始，0 到 4294967295。

2. 计算中点。

3. 循环遍历文件，计算有多少个数字等于、小于或高于中点值。

4. 如果没有相同的数字，那么就完成了。中点数字就是答案。

5. 否则，选择数字最少的范围，并使用此新范围从步骤 2 重复。

这将需要对文件进行最多 32 次线性扫描，但它只会使用几个字节的内存来存储范围和计数。

这本质上与 Henning 的解决方案，只不过它使用两个 bin 而不是 16k。

Answer 9

编辑 好吧，这并没有经过深思熟虑，因为它假设文件中的整数遵循某种静态分布。显然他们不需要这样做，但即便如此，人们也应该尝试一下这个：

---

有大约 43 亿个 32 位整数。我们不知道它们在文件中的分布情况，但最坏的情况是香农熵最高的情况：均匀分布。在这种情况下，文件中任何一个整数不出现的概率为

( (2³²-1)/2³² )⁴ ⁰⁰⁰ ⁰⁰⁰ ⁰⁰⁰ ≈ .4

香农熵越低，平均概率就越高，但即使对于这种最坏的情况，我们有 90% 的机会找到 5 之后不出现的数字用随机整数进行猜测。只需使用伪随机生成器创建这样的数字，并将它们存储在列表中。然后依次读取 int 并将其与您的所有猜测进行比较。当存在匹配项时，删除此列表条目。浏览完所有文件后，您很可能会留下不止一种猜测。使用其中任何一个。在极少数情况下（即使在最坏的情况下也是 10%）无法猜测的情况下，获取一组新的随机整数，这次可能更多（10->99%）。

内存消耗：几十个字节，复杂度：O(n)，开销：不可避免，因为大部分时间都花在不可避免的硬盘访问上，而不是比较整数。

---

The actual worst case, when we do not assume a static distribution, is that every integer occurs max. once, because then only
1 - 4000000000/2³² ≈ 6%
of all integers don't occur in the file. So you'll need some more guesses, but that still won't cost hurtful amounts of memory.

Answer 10

如果 [0, 2^x - 1] 范围内缺少一个整数，则只需将它们全部异或即可。例如：（

>>> 0 ^ 1 ^ 3
2
>>> 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 6 ^ 7
5

我知道这并不能完全回答这个问题，但对于一个非常相似的问题来说，这是一个很好的答案。）

Answer 11

他们可能想看看您是否听说过概率布隆过滤器，它可以非常有效地绝对确定某个值是否不存在一个大集合的一部分，（但只能以高概率确定它是该集合的成员。）

Answer 12

根据原问题当前的措辞，最简单的解决方案是：

找到文件中的最大值，然后加1。

Answer 13

使用BitSet。将 40 亿个整数（假设最多 2^32 个整数）按每字节 8 个打包到 BitSet 中，大小为 2^32 / 2^3 = 2^29 = 大约 0.5 Gb。

要添加更多细节 - 每次读取数字时，请在 BitSet 中设置相应的位。然后，遍历 BitSet 以查找第一个不存在的数字。事实上，您可以通过重复选择随机数并测试它是否存在来同样有效地做到这一点。

实际上 BitSet.nextClearBit(0) 会告诉您第一个未设置的位。

查看 BitSet API，它似乎只支持 0..MAX_INT，因此您可能需要 2 个 BitSets - 一个用于 +'ve 数字，一个用于 -ve 数字 - 但内存要求不会改变。

Answer 14

如果没有大小限制，最快的方法是获取文件的长度，并生成文件的长度+1个随机数字（或只是“11111...”）。优点：您甚至不需要读取文件，并且可以将内存使用量降至几乎为零。缺点：您将打印数十亿个数字。

但是，如果唯一的因素是最大限度地减少内存使用，而其他都不重要，那么这将是最佳解决方案。它甚至可能会让你获得“最严重滥用规则”奖。

Answer 15

如果我们假设数字的范围始终为 2^n（2 的偶次幂），则异或将起作用（如另一张海报所示）。至于为什么，让我们来证明一下：

理论

给定任何基于 0 的整数范围，其中包含 2^n 元素且缺少一个元素，您可以通过简单地对已知值进行异或来找到缺少的元素一起得出缺失的数字。

证明

让我们看一下 n = 2。对于 n=2，我们可以表示 4 个唯一的整数：0、1、2、3。它们的位模式为：

• 0 - 00
• 1 - 01
• 2 - 10
• 3 - 11

现在，如果我们观察的话，每一位都被设置了两次。因此，由于它被设置为偶数次，因此数字的异或将产生 0。如果缺少单个数字，则异或将产生一个数字，当与丢失的数字进行异或时将产生0。因此，缺失的数与异或所得的数完全相同。如果我们删除 2，则生成的异或将为 10（或 2）。

现在，让我们看看n+1。让我们分别调用n、x中每个位被设置的次数以及n+1中每个位被设置的次数y。 y 的值将等于 y = x * 2，因为有 x 个元素的 n+1 > 位设置为 0，x 元素的 n+1 位设置为 1。由于 2x 始终为偶数，n+1 将始终使每个位设置偶数次。

因此，由于 n=2 有效，并且 n+1 有效，因此异或方法将适用于 n>=2 的所有值。

基于 0 的范围的算法

这非常简单。它使用 2*n 位内存，因此对于任何范围 <= 32，2 个 32 位整数都可以工作（忽略文件描述符消耗的任何内存）。它对文件进行了一次传递。

long supplied = 0;
long result = 0;
while (supplied = read_int_from_file()) {
    result = result ^ supplied;
}
return result;

任意范围的算法

该算法适用于任何起始数字到任何结束数字的范围，只要总范围等于 2^n...这基本上将范围重新设置为最小值为 0。但它确实需要两次遍历文件（第一次获取最小值，第二次计算丢失的整数）。

long supplied = 0;
long result = 0;
long offset = INT_MAX;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    result = result ^ (supplied - offset);
}
return result + offset;

任意范围

我们可以将此修改后的方法应用于一组任意范围，因为所有范围都会至少跨越 2^n 的幂一次。仅当有一个缺失位时，此方法才有效。它需要对未排序的文件进行 2 次传递，但每次都会找到单个缺失的数字：

long supplied = 0;
long result = 0;
long offset = INT_MAX;
long n = 0;
double temp;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    n++;
    result = result ^ (supplied - offset);
}
// We need to increment n one value so that we take care of the missing 
// int value
n++
while (n == 1 || 0 != (n & (n - 1))) {
    result = result ^ (n++);
}
return result + offset;

基本上，将范围重新设置为 0 附近。然后，它在计算异或时计算要附加的未排序值的数量。然后，它将未排序值的计数加 1 以处理缺失值（计算缺失值）。然后，继续对 n 值进行异或，每次增加 1，直到 n 是 2 的幂。然后将结果重新基回原始基数。完毕。

这是我在 PHP 中测试的算法（使用数组而不是文件，但概念相同）：

function find($array) {
    $offset = min($array);
    $n = 0;
    $result = 0;
    foreach ($array as $value) {
        $result = $result ^ ($value - $offset);
        $n++;
    }
    $n++; // This takes care of the missing value
    while ($n == 1 || 0 != ($n & ($n - 1))) {
        $result = $result ^ ($n++);
    }
    return $result + $offset;
}

将任意范围的值（我测试过包括负数）放入一个数组中，其中一个在该范围内缺失，它找到了正确的值每次。

另一种方法

既然我们可以使用外部排序，为什么不直接检查间隙呢？如果我们假设文件在运行该算法之前已排序：

long supplied = 0;
long last = read_int_from_file();
while (supplied = read_int_from_file()) {
    if (supplied != last + 1) {
        return last + 1;
    }
    last = supplied;
}
// The range is contiguous, so what do we do here?  Let's return last + 1:
return last + 1;

Answer 16

棘手的问题，除非引用不当。只需读取一次文件即可获取最大整数n，并返回n+1。

当然，您需要一个备份计划，以防 n+1 导致整数溢出。

Answer 17

检查输入文件的大小，然后输出任何数字，该数字太大而无法用该大小的文件表示。这似乎是一个廉价的技巧，但它是一个面试问题的创造性解决方案，它巧妙地回避了内存问题，而且从技术上讲它是 O(n) 的。

void maxNum(ulong filesize)
{
    ulong bitcount = filesize * 8; //number of bits in file

    for (ulong i = 0; i < bitcount; i++)
    {
        Console.Write(9);
    }
}

应打印 10 ^bitcount - 1，它始终大于 2 ^bitcount。从技术上讲，您必须击败的数字是 2 ^bitcount - (4 * 10⁹ - 1)，因为您知道有 (40 亿- 1) 文件中的其他整数，即使完美压缩，它们也将至少占用一位。

Answer 18

• 最简单的方法是找到文件中的最小数字，并返回比该数字少的 1。对于包含 n 个数字的文件，这使用 O(1) 存储空间和 O(n) 时间。但是，如果数字范围有限，则会失败，这可能会使 min-1 不是数字。

• 使用位图的简单直接的方法已经提到过。该方法使用 O(n) 时间和存储。

• 还提到了具有 2^16 个计数桶的 2-pass 方法。它读取 2*n 个整数，因此使用 O(n) 时间和 O(1) 存储，但它无法处理超过 2^16 个数字的数据集。然而，通过运行 4 次而不是 2 次，它可以轻松扩展到（例如）2^60 64 位整数，并且通过仅使用内存中适合的 bin 并相应地增加传递数量，可以轻松适应使用微小内存。这种情况下运行时间不再是 O(n) 而是 O(n*log n)。

• 将所有数字异或在一起的方法，迄今为止由 rfrankel 提到，并由 ircmaxell 详细回答了 stackoverflow#35185，正如 ltn100 指出的那样。它使用 O(1) 存储和 O(n) 运行时间。如果目前我们假设 32 位整数，XOR 有 7% 的概率产生不同的数字。基本原理：给定〜4G不同的数字异或在一起，并且大约。 300M不在文件中，每个位位置设置的位数有相同的奇数或偶数机会。因此，2^32 个数字作为 XOR 结果出现的可能性相同，其中 93% 已在文件中。请注意，如果文件中的数字并非全部不同，则 XOR 方法的成功概率会上升。

Answer 19

从文件中删除空格和非数字字符并附加 1。您的文件现在包含原始文件中未列出的单个数字。

来自 Carbonetc 的 Reddit。

Answer 20

出于某种原因，我一读到这个问题就想到了对角化。我假设任意大的整数。

读出第一个数字。向左填充零位，直到达到 40 亿位。如果第一个（高位）位为0，则输出1；否则输出 0。（您实际上不必左填充：如果数字中没有足够的位，您只需输出 1。）对第二个数字执行相同的操作，除了使用其第二位。以这种方式继续浏览该文件。您将一次一位地输出 40 亿位数，并且该数字不会与文件中的任何数字相同。证明：它与第 n 个数字相同，那么他们会在第 n 位上达成一致，但通过构造却无法达成一致。

Answer 21

您可以使用位标志来标记整数是否存在。

遍历整个文件后，扫描每一位以确定该数字是否存在。

假设每个整数都是 32 位，如果完成了位标记，它们将方便地装入 1 GB RAM。

Answer 22

为了完整起见，这是另一个非常简单的解决方案，它很可能需要很长时间才能运行，但使用的内存很少。

令所有可能的整数的范围为 int_min 到 int_max，并且
bool isNotInFile(integer) 一个函数，如果文件不包含某个整数，则返回 true，否则返回 false（通过将该特定整数与文件中的每个整数进行比较）

for (integer i = int_min; i <= int_max; ++i)
{
    if (isNotInFile(i)) {
        return i;
    }
}

Answer 23

对于 10 MB 内存限制：

1. 将数字转换为其二进制表示形式。
2. 创建一棵二叉树，其中 left = 0 且 right = 1。
3. 使用其二进制表示形式将每个数字插入树中。
4. 如果已经插入了数字，则叶子已经被创建。

完成后，就走一条之前没有创建过的路径来创建请求的数字。

40 亿个数字 = 2^32，这意味着 10 MB 可能不够。

编辑

可以进行优化，如果两端叶子已创建并且具有共同的父级，则可以将它们删除并将父级标记为不是解决方案。这会减少分支并减少对内存的需求。

编辑 II

也不需要完全构建树。仅当数字相似时才需要构建深层分支。如果我们也砍掉树枝，那么这个解决方案实际上可能有效。

Answer 24

我将回答1GB版本：

问题中没有足够的信息，所以我将首先陈述一些假设：

整数是32位，范围-2,147,483,648到2,147,483,647。

伪代码：

var bitArray = new bit[4294967296];  // 0.5 GB, initialized to all 0s.

foreach (var number in file) {
    bitArray[number + 2147483648] = 1;   // Shift all numbers so they start at 0.
}

for (var i = 0; i < 4294967296; i++) {
    if (bitArray[i] == 0) {
        return i - 2147483648;
    }
}

Answer 25

正如 Ryan 所说，基本上，对文件进行排序，然后遍历整数，当跳过一个值时，您就得到了它:)

编辑在反对者处：OP提到可以对文件进行排序，所以这是一个有效的方法。

Answer 26

只要我们在做创造性的答案，这里就有另一个答案。

使用外部排序程序对输入文件进行数字排序。这适用于您可能拥有的任何内存量（如果需要，它将使用文件存储）。
通读已排序的文件并输出第一个缺少的数字。

Answer 27

位消除

一种方法是消除位，但这实际上可能不会产生结果（很可能不会）。伪代码：

long val = 0xFFFFFFFFFFFFFFFF; // (all bits set)
foreach long fileVal in file
{
    val = val & ~fileVal;
    if (val == 0) error;
}

位计数

跟踪位计数；并使用数量最少的位来生成一个值。同样，这并不能保证生成正确的值。

范围逻辑

跟踪列表排序范围（按开始排序）。范围由结构定义：

struct Range
{
  long Start, End; // Inclusive.
}
Range startRange = new Range { Start = 0x0, End = 0xFFFFFFFFFFFFFFFF };

遍历文件中的每个值并尝试将其从当前范围中删除。此方法没有内存保证，但效果应该不错。

Answer 28

2^128*1018 + 1（即 (2⁸)^{16*1018< /sup> + 1 ) - 这不能成为今天的通用答案吗？这表示 16 EB 文件无法容纳的数字，这是当前任何文件系统中的最大文件大小。}

Answer 29

我认为这是一个已解决的问题（见上文），但有一个有趣的副作用需要记住，因为它可能会被问到：

如果正好有 4,294,967,295 (2^32 - 1) 32 位整数，没有重复，因此只缺少一个，有一个简单的解决方案。

从零开始运行总计，对于文件中的每个整数，添加具有 32 位溢出的整数（实际上，runningTotal = (runningTotal + nextInteger) % 4294967296）。完成后，将 4294967296/2 添加到运行总数中，再次出现 32 位溢出。用 4294967296 减去这个值，结果就是缺失的整数。

“仅缺少一个整数”问题只需运行一次即可解决，并且只有 64 位 RAM 专用于数据（32 位用于运行总计，32 位用于读取下一个整数）。

推论：如果我们不关心整数结果必须有多少位，则更通用的规范非常容易匹配。我们只是生成一个足够大的整数，它不能包含在我们给定的文件中。同样，这占用的 RAM 绝对是最小的。请参阅伪代码。

# Grab the file size
fseek(fp, 0L, SEEK_END);
sz = ftell(fp);
# Print a '2' for every bit of the file.
for (c=0; c<sz; c++) {
  for (b=0; b<4; b++) {
    print "2";
  }
}

Answer 30

如果您不假设 32 位约束，则只需返回随机生成的 64 位数字（如果您是悲观主义者，则返回 128 位）。发生碰撞的几率为 1 in 2^64/(4*10^9) = 4611686018.4（大约为 40 亿分之一）。大多数时候你是对的！

（开玩笑……有点。）