简单的面试问题变得更难：给定数字 1..100，在给定 k 个缺失的情况下找到缺失的数字

不久前我有过一次有趣的求职面试经历。这个问题一开始很简单：

Q1：我们有一个装有数字的袋子1, 2, 3, …, 100。每个数字只出现一次，所以有 100 个数字。现在从袋子里随机选出一个号码。找到丢失的号码。

当然，我以前听说过这个面试问题，所以我很快就回答了以下内容：

A1: 嗯，数字的总和1 + 2 + 3 + … + N is (N+1)(N/2) (see 维基百科：算术级数之和 http://en.wikipedia.org/wiki/Arithmetic_sum#Sum). For N = 100，总和是5050.

因此，如果袋子中存在所有数字，则总和将恰好为5050。由于缺少一个数字，因此总和将小于此数字，差值就是该数字。所以我们可以找到缺失的数字O(N)时间和O(1) space.

到这里我以为自己已经做得很好了，但是突然问题来了个意想不到的转折：

Q2：这是正确的，但现在如果TWO数字缺失？

我以前从未见过/听说过/考虑过这种变化，所以我惊慌失措，无法回答这个问题。面试官坚持要了解我的思考过程，所以我提到也许我们可以通过与预期产品进行比较来获得更多信息，或者可能在从第一遍收集了一些信息后进行第二遍等等，但我真的只是在拍摄在黑暗中而不是实际上有一条清晰的解决方案。

面试官确实试图鼓励我，说拥有第二个方程确实是解决问题的一种方法。此时我有点沮丧（因为事先不知道答案），并询问这是否是一种通用的（读：“有用的”）编程技术，或者它是否只是一个技巧/陷阱的答案。

面试官的回答令我惊讶：你可以推广该技术来找到 3 个缺失的数字。事实上，你可以概括它来找到k缺少数字。

Qk: 如果确实如此k包里的号码不见了，你如何有效地找到它？

这是几个月前的事了，我仍然不明白这个技术是什么。显然有一个Ω(N)时间下限，因为我们必须至少扫描一次所有数字，但面试官坚持认为TIME and SPACE求解技术的复杂性（减去O(N)时间输入扫描）定义在k not N.

所以这里的问题很简单：

• 你会如何解决Q2?
• 你会如何解决Q3?
• 你会如何解决Qk?

澄清

• 一般有N数字从 1..N，不仅仅是 1..100。
• 我并不是在寻找明显的基于集合的解决方案，例如用一个bit set http://en.wikipedia.org/wiki/Bit_array，通过指定位的值对每个数字的存在/不存在进行编码，因此使用O(N)额外空间中的位。我们无法承担与以下比例成比例的任何额外空间N.
• 我也不是在寻找明显的排序优先方法。这种方法和基于集合的方法在采访中值得一提（它们很容易实现，并且取决于N，非常实用）。我正在寻找圣杯解决方案（它可能会也可能不会实际实施，但仍然具有所需的渐近特性）。

所以同样，你当然必须扫描输入O(N)，但您只能捕获少量信息（定义为k not N），然后必须找到k不知何故缺少数字。

这里有一个总结迪米特里斯·安德烈欧 https://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-number/3492664#3492664 .

记住 i 次方的和，其中 i=1,2,..,k。这将问题简化为求解方程组

a₁ + a₂ + ... + a_k = b₁

a₁² + a₂² + ... + a_k² = b₂

...

a₁^k + a₂^k + ... + a_k^k = b_k

Using Newton's identities https://en.wikipedia.org/wiki/Newton_identities#Formulation_in_terms_of_symmetric_polynomials, knowing b_i allows to compute

c₁ = a₁ + a₂ + ... a_k

c₂ = a₁a₂ + a₁a₃ + ... + a_k-1a_k

...

c_k = a₁a₂ ... a_k

If you expand the polynomial (x-a₁)...(x-a_k) the coefficients will be exactly c₁, ..., c_k - see Viète's formulas https://en.wikipedia.org/wiki/Vi%C3%A8te's_formulas. Since every polynomial factors uniquely (ring of polynomials is an Euclidean domain https://en.wikipedia.org/wiki/Euclidean_domain), this means a_i are uniquely determined, up to permutation.

这就证明了记住幂就足以恢复数字。对于常数 k，这是一个很好的方法。

However, when k is varying, the direct approach of computing c₁,...,c_k is prohibitely expensive, since e.g. c_k is the product of all missing numbers, magnitude n!/(n-k)!. To overcome this, perform computations in Zq field https://en.wikipedia.org/wiki/Finite_field_arithmetic, where q is a prime such that n <= q < 2n - it exists by Bertrand's postulate https://en.wikipedia.org/wiki/Bertrand's_postulate. The proof doesn't need to be changed, since the formulas still hold, and factorization of polynomials is still unique. You also need an algorithm for factorization over finite fields, for example the one by Berlekamp https://en.wikipedia.org/wiki/Berlekamp's_algorithm or Cantor-Zassenhaus https://en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_algorithm.

常数 k 的高级伪代码：

• 计算给定数字的 i 次方
• Subtract to get sums of i-th powers of unknown numbers. Call the sums b_i.
• Use Newton's identities to compute coefficients from b_i; call them c_i. Basically, c₁ = b₁; c₂ = (c₁b₁ - b₂)/2; see Wikipedia for exact formulas
• Factor the polynomial x^k-c₁x^k-1 + ... + c_k.
• The roots of the polynomial are the needed numbers a₁, ..., a_k.

对于变化的 k，使用例如找到素数 n

EDIT: The previous version of this answer stated that instead of Z_q, where q is prime, it is possible to use a finite field of characteristic 2 (q=2^(log n)). This is not the case, since Newton's formulas require division by numbers up to k.