algorithm - 二进制字符串的线性算法

Question

我正在经历一些旧的期中考试来学习。 (没有给出解决方案)

我遇到了这个问题，一直卡在上面

5. Let n = 2^ℓ − 1 for some positive integer ℓ. Suppose someone claims to hold an array A[1.. n] of distinct ℓ-bit strings; thus, exactly one ℓ-bit string does not appear in A. Suppose further that the only way we can access A is by calling the function FetchBit(i, j), which returns the j^th bit of the string A[i] in O(1) time.
   Describe an algorithm to find the missing string in A using only O(n) calls to FetchBit.

我唯一能想到的就是遍历每个字符串，将其转换为以 10 为基数，对它们进行排序，然后查看缺少哪个值。但这肯定不是 O(n)

证明这不是家庭作业... http://web.engr.illinois.edu/~jeffe/teaching/algorithms/hwex/f12/midterm1.pdf

Answer 1

您可以在 2n 次操作中完成。

首先，查看每个数字的第一位。显然，您将得到 2^ℓ-1 个零和 2^ℓ-1-1 个，反之亦然(因为只缺少一个数字)。如果有 2^ℓ-1-1 那么你知道缺失数字的第一位是 1，否则就是零。

现在您知道缺失数字的第一位了。让我们看看所有具有相同第一位的数字(其中有 2^ℓ-1-1)并用它们的第二位重复相同的过程。这样您将确定缺失数字的第二位，依此类推。

FetchBit 调用的总数将为 2^ℓ-1 + 2^ℓ-1-1 + ... + 2¹ -1 <= 2^ℓ+1 <= 2n+2 = O(n).