不能由数组中的数字和构成的最小数

This problem was asked to me in Amazon interview -

这个问题在亚马逊的采访中被问到

Given a array of positive integers, you have to find the smallest positive integer that can not be formed from the sum of numbers from array.

给定一个正整数数组，您必须找到最小的正整数，这个正整数不能由数组中的数字和组成。

Example:

例子:

Array:[4 13 2 3 1]
result= 11 { Since 11 was smallest positive number which can not be formed from the given array elements }

What i did was :

我所做的是:

1. sorted the array
2. 排序数组
3. calculated the prefix sum
4. 计算了前缀和
5. Treverse the sum array and check if next element is less than 1 greater than sum i.e. A[j]<=(sum+1). If not so then answer would be sum+1
6. 遍历和数组，检查下一个元素是否小于1，即A[j]<=(sum+1)。如果不是，那么答案是和+1

But this was nlog(n) solution.

但这是nlog(n)解。

Interviewer was not satisfied with this and asked a solution in less than O(n log n) time.

面试官对这一点并不满意，并在不到O(n log n)的时间内提出了一个解决方案。

3 个解决方案

#1

Consider all integers in interval [2ⁱ .. 2ⁱ⁺¹ - 1]. And suppose all integers below 2ⁱ can be formed from sum of numbers from given array. Also suppose that we already know C, which is sum of all numbers below 2ⁱ. If C >= 2ⁱ⁺¹ - 1, every number in this interval may be represented as sum of given numbers. Otherwise we could check if interval [2ⁱ .. C + 1] contains any number from given array. And if there is no such number, C + 1 is what we searched for.

考虑区间内的所有整数[2i ..2我+ 1 - 1)。假设2i以下的所有整数都可以由给定数组中的数字之和构成。假设我们已经知道C，它是2i以下所有数的和。如果C >= 2i+1 - 1，则该区间内的每个数字都可以表示为给定数字的和。否则我们可以检查interval是否为2i。C + 1]包含给定数组中的任何数字。如果没有这个数，C + 1就是我们要找的。

Here is a sketch of an algorithm:

这是一个算法的草图:

1. For each input number, determine to which interval it belongs, and update corresponding sum: S[int_log(x)] += x.
2. 对于每个输入数字，确定其所属的间隔，并更新相应的和:S[int_log(x)] += x。
3. Compute prefix sum for array S: foreach i: C[i] = C[i-1] + S[i].
4. 计算数组S: foreach i: C[i] = C[i-1] + S[i]的前缀和。
5. Filter array C to keep only entries with values lower than next power of 2.
6. 过滤数组C，只保留值小于2次幂的项。
7. Scan input array once more and notice which of the intervals [2ⁱ .. C + 1] contain at least one input number: i = int_log(x) - 1; B[i] |= (x <= C[i] + 1).
8. 再扫描一次输入数组，注意哪个区间[2i .]C + 1]包含至少一个输入号:i = int_log(x) - 1;B[i] |= (x <= C[i] + 1)。
9. Find first interval that is not filtered out on step #3 and corresponding element of B[] not set on step #4.
10. 在第3步中找到没有被过滤掉的第一个间隔，并且在第4步没有设置相应的B[]元素。

If it is not obvious why we can apply step 3, here is the proof. Choose any number between 2ⁱ and C, then sequentially subtract from it all the numbers below 2ⁱ in decreasing order. Eventually we get either some number less than the last subtracted number or zero. If the result is zero, just add together all the subtracted numbers and we have the representation of chosen number. If the result is non-zero and less than the last subtracted number, this result is also less than 2ⁱ, so it is "representable" and none of the subtracted numbers are used for its representation. When we add these subtracted numbers back, we have the representation of chosen number. This also suggests that instead of filtering intervals one by one we could skip several intervals at once by jumping directly to int_log of C.

如果不清楚为什么我们可以申请第3步，这就是证明。在2i和C之间选择任意一个数，然后按降序减去2i以下的所有数。最终我们会得到一个小于最后一个减数的数或者是零。如果结果是零，把所有的减数相加，我们就得到了所选数字的表示形式。如果结果是非零且小于最后一个减数，那么这个结果也小于2i，因此它是“可表示的”，并且没有一个减数用于它的表示。当我们把这些减数相加，我们就得到了所选数字的表示。这也表明，我们可以直接跳到int_log (C)，而不是逐一过滤间隔，一次跳过几个间隔。

Time complexity is determined by function int_log(), which is integer logarithm or index of the highest set bit in the number. If our instruction set contains integer logarithm or any its equivalent (count leading zeros, or tricks with floating point numbers), then complexity is O(n). Otherwise we could use some bit hacking to implement int_log() in O(log log U) and obtain O(n * log log U) time complexity. (Here U is largest number in the array).

时间复杂度由函数int_log()决定，它是整数对数或数字中最高设置位的索引。如果我们的指令集包含整数对数或它的任何等价的(计数前导零，或者浮点数的技巧)，那么复杂度是O(n)。否则，我们可以使用一些位黑客技术在O(log U)中实现int_log()并获得O(n * log log U)时间复杂度。(这里U是数组中最大的数)

If step 1 (in addition to updating the sum) will also update minimum value in given range, step 4 is not needed anymore. We could just compare C[i] to Min[i+1]. This means we need only single pass over input array. Or we could apply this algorithm not to array but to a stream of numbers.

如果步骤1(除了更新和之外)也将更新给定范围内的最小值，则不再需要步骤4。我们可以比较C[i]和Min[i+1]。这意味着我们只需要对输入数组进行一次传递。或者我们可以不把这个算法应用到数组而是应用到数字流中。

Several examples:

几个例子:

Input:       [ 4 13  2  3  1]    [ 1  2  3  9]    [ 1  1  2  9]
int_log:       2  3  1  1  0       0  1  1  3       0  0  1  3

int_log:     0  1  2  3          0  1  2  3       0  1  2  3
S:           1  5  4 13          1  5  0  9       2  2  0  9
C:           1  6 10 23          1  6  6 15       2  4  4 13
filtered(C): n  n  n  n          n  n  n  n       n  n  n  n
number in
[2^i..C+1]:  2  4  -             2  -  -          2  -  -
C+1:              11                7                5

For multi-precision input numbers this approach needs O(n * log M) time and O(log M) space. Where M is largest number in the array. The same time is needed just to read all the numbers (and in the worst case we need every bit of them).

对于多精度输入数，这种方法需要O(n * log M)时间和O(log M)空间。其中M是数组中最大的数。同样的时间只需要读取所有的数字(在最坏的情况下，我们需要它们的每一点)。

Still this result may be improved to O(n * log R) where R is the value found by this algorithm (actually, the output-sensitive variant of it). The only modification needed for this optimization is instead of processing whole numbers at once, process them digit-by-digit: first pass processes the low order bits of each number (like bits 0..63), second pass - next bits (like 64..127), etc. We could ignore all higher-order bits after result is found. Also this decreases space requirements to O(K) numbers, where K is number of bits in machine word.

仍然可以将这个结果改进为O(n * log R)，其中R是该算法找到的值(实际上是该算法的输出敏感变量)。这个优化所需要的唯一修改不是一次处理整个数字，而是按数字进行处理:第一次传递处理每个数字的低阶位(如位0..63)，第二次传递-下一个位(如64..127)，等等。这也降低了对O(K)数的空间要求，其中K是机器字中的位数。

#2

There's a beautiful algorithm for solving this problem in time O(n + Sort), where Sort is the amount of time required to sort the input array.

有一个很好的算法可以在O(n + Sort)时间内解决这个问题，其中Sort是对输入数组进行排序所需的时间。

The idea behind the algorithm is to sort the array and then ask the following question: what is the smallest positive integer you cannot make using the first k elements of the array? You then scan forward through the array from left to right, updating your answer to this question, until you find the smallest number you can't make.

算法背后的思想是对数组进行排序，然后问这样一个问题:使用数组的前k个元素不能生成的最小正整数是多少?然后从左到右扫描数组，更新您对这个问题的答案，直到找到无法生成的最小数字。

Here's how it works. Initially, the smallest number you can't make is 1. Then, going from left to right, do the following:

这是它是如何工作的。一开始，你做不到的最小的数是1。然后，从左到右，做以下事情:

• If the current number is bigger than the smallest number you can't make so far, then you know the smallest number you can't make - it's the one you've got recorded, and you're done.
• 如果当前的数字大于目前为止你做不到的最小的数字，那么你就知道你做不到的最小的数字——这是你已经记录的数字，你完成了。
• Otherwise, the current number is smaller than the smallest number you can't make. The claim is that you can indeed make this number. Right now, you know the smallest number you can't make with the first k elements of the array (call it candidate) and are now looking at value A[k]. The number candidate - A[k] therefore must be some number that you can indeed make with the first k elements of the array, since otherwise candidate - A[k] would be a smaller number than the smallest number you allegedly can't make with the first k numbers in the array. Moreover, you can make any number in the range candidate to candidate + A[k], inclusive, because you can start with any number in the range from 1 to A[k], inclusive, and then add candidate - 1 to it. Therefore, set candidate to candidate + A[k] and increment k.
• 否则，当前的数字将小于无法生成的最小数字。它的意思是你确实可以得出这个数字。现在，您已经知道了数组的前k个元素(称为候选元素)不能生成的最小数字，现在正在查看值A[k]。因此，A[k]一定是你可以用数组的第k个元素来做的一个数字，因为如果不是这样的话，A[k]将会比你所声称的在数组中第一个k个数字所不能做的最小的数字小。而且，你可以在候选人+ A[k]的范围内取任何数字，包括在内，因为你可以从1到A[k]的范围内取任何数字，包括，然后加上候选人- 1。因此，将候选者设置为候选者+ A[k]，增加k。

In pseudocode:

在伪代码:

Sort(A)
candidate = 1
for i from 1 to length(A):
   if A[i] > candidate: return candidate
   else: candidate = candidate + A[i]
return candidate

Here's a test run on [4, 13, 2, 1, 3]. Sort the array to get [1, 2, 3, 4, 13]. Then, set candidate to 1. We then do the following:

这是对[4,13,2,1,3]的测试运行。对数组进行排序，得到[1,2,3,4,13]。然后，将候选者设置为1。然后我们做以下工作:

• A[1] = 1, candidate = 1:
  • A[1] ≤ candidate, so set candidate = candidate + A[1] = 2
  • [1]≤候选人,所以候选人=候选人+[1]= 2
• [1]= 1,候选人= 1:[1]≤候选人,所以候选人=候选人+[1]= 2
• A[2] = 2, candidate = 2:
  • A[2] ≤ candidate, so set candidate = candidate + A[2] = 4
  • [2]≤候选人,所以候选人=候选人+[2]= 4
• [2]= 2,候选人= 2:[2]≤候选人,候选人=候选人+[2]= 4
• A[3] = 3, candidate = 4:
  • A[3] ≤ candidate, so set candidate = candidate + A[3] = 7
  • [3]≤候选人,所以设置候选人=候选人+[3]= 7
• [3]= 3,候选人= 4:[3]≤候选人,候选人=候选人+[3]= 7
• A[4] = 4, candidate = 7:
  • A[4] ≤ candidate, so set candidate = candidate + A[4] = 11
  • [4]≤候选人,所以设置候选人=候选人+[4]= 11
• [4]= 4,候选人= 7:[4]≤候选人,候选人=候选人+[4]= 11
• A[5] = 13, candidate = 11:
  • A[4] > candidate, so return candidate (11).
  • [4] >候选，返回候选(11)
• [5] = 13，候选者= 11:[4]>候选者，因此返回候选者(11)。

So the answer is 11.

所以答案是11。

The runtime here is O(n + Sort) because outside of sorting, the runtime is O(n). You can clearly sort in O(n log n) time using heapsort, and if you know some upper bound on the numbers you can sort in time O(n log U) (where U is the maximum possible number) by using radix sort. If U is a fixed constant, (say, 10⁹), then radix sort runs in time O(n) and this entire algorithm then runs in time O(n) as well.

这里的运行时是O(n + Sort)因为除了排序，运行时是O(n)你可以用heapsort对O(n log n)时间进行排序，如果你知道数字上的某个上界，你可以用基数排序来对O(n log U)(其中U是可能的最大数字)进行排序。如果U是一个固定的常数(比如109)，那么基数排序在O(n)时间内运行，整个算法也在O(n)时间内运行。

Hope this helps!

希望这可以帮助!

#3

Use bitvectors to accomplish this in linear time.

使用位向量在线性时间内完成。

Start with an empty bitvector b. Then for each element k in your array, do this:

从一个空的位向量b开始，然后对数组中的每个元素k做如下操作:

b = b | b << k | 2^(k-1)

b = | b < < k | 2 ^(k - 1)

To be clear, the i'th element is set to 1 to represent the number i, and | k is setting the k-th element to 1.

要明确的是，第i个元素被设置为1以表示数字i， |k将第k个元素设置为1。

After you finish processing the array, the index of the first zero in b is your answer (counting from the right, starting at 1).

在处理完数组之后，b中第一个0的索引就是你的答案(从右边开始，从1开始)。

1. b=0
2. b = 0
3. process 4: b = b | b<<4 | 1000 = 1000
4. 流程4:b = b | b<<4 | 1000 = 1000。
5. process 13: b = b | b<<13 | 1000000000000 = 10001000000001000
6. 工艺13:b = b | b< 13 | 1000000000000 = 100010001000100010001000000001000
7. process 2: b = b | b<<2 | 10 = 1010101000000101010
8. 工艺2:b = b | b< 2 | 10 = 101010101010000001010
9. process 3: b = b | b<<3 | 100 = 1011111101000101111110
10. 流程3:b = b | b< 3 | 100 = 1011111111010001011110
11. process 1: b = b | b<<1 | 1 = 11111111111001111111111
12. 流程1:b = b | b< 1 | 1 = 1111111111111111111001111111111

First zero: position 11.

第一个零:11。