不能从数字的总和形成了从阵列最小的数 [英] Smallest number that can not be formed from sum of numbers from array

问题描述

这个问题问我，亚马逊的采访 -

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.

例如：

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. 排序的数组
2. 计算的preFIX总和
3. Treverse总和阵列，并检查是否下一个元素是小于1 大于总结即A [J]＆LT; =（总和+ 1）。如果不是这样，然后回答会 是之和+ 1

1. sorted the array
2. calculated the prefix sum
3. 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

但是，这是n日志（n）的解决方案。

But this was nlog(n) solution.

记者并不满​​足于这一点，并问了一个解决方案，在不到为O（n log n）的时间。

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

推荐答案

考虑所有整数区间[2 ^我。2 ^{I + 1} - 1]。再假设下面的所有整数2 ^我可以从给定数组数的总和形成。另外，假定我们已经知道C，这是所有数字之和低于2 ^我。如果C> = 2 ^{i + 1的功能} - 1，在此区间的每个数字可以被重新presented作为已知数的总和。否则，我们可以检查是否区间[2 ^我 .. C + 1]包含任何数量从给定的数组。并且如果不存在这样的数，C + 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.

下面是一个算法的草图：

Here is a sketch of an algorithm:

1. 对于每个输入数量，确定哪个区间所属，和更新相应的总和： S [int_log（X）] + = X
2. 计算preFIX总和阵列S：的foreach我：C [i] = C [I-1] + S [I]
3. 在滤镜阵列C到只保留条目值低于2下一个动力。
4. 在扫描输入数组一次，并通知该区间[2 ^我 .. C + 1]至少包含一个输入编号： I = int_log（X） - 1; B〔I] | =（X＆LT; = C [I] + 1）。
5. 找到了没有被过滤掉的步骤＃3和的相应元素b [] 不是在第4步设置第一个间隔。

1. For each input number, determine to which interval it belongs, and update corresponding sum: S[int_log(x)] += x.
2. Compute prefix sum for array S: foreach i: C[i] = C[i-1] + S[i].
3. Filter array C to keep only entries with values lower than next power of 2.
4. 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).
5. Find first interval that is not filtered out on step #3 and corresponding element of B[] not set on step #4.

如果这不是显而易见的，为什么我们可以申请第3步，这里是证明。按递减顺序选择以下2 ^我 2 ^我和C，然后依次从它减去所有的号码之间的任何数字。最终，我们既取得比上消减数量或零一定数量的少。如果结果是零，只是添加了所有的数字中减去，我们有选择的号码重新presentation。如果结果为非零且小于最后消减数目，这样的结果也是小于2 ^I ，因此它是重新presentable并且没有一个减去号码被用于其重新presentation。当我们添加这些减去的数字后面，我们有选择的号码重新presentation。这也表明，而不是过滤间隔一个接一个，我们可以跳过几个间隔一次直接跳到int_log了C。

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.

时间复杂度由功能决定的 int_log（），这是整数对数或人数最高设置位的索引。如果我们的指令集包含整数对数或同等学历（计数前导零，或浮点数的技巧），那么复杂度为O（N）。否则，我们可以使用一些位黑客实施 int_log（）在为O（log日志U），并获得为O（n *日志记录U）的时间复杂度。 （这里U是数组中的最大数）。

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).

如果步骤1（除了更新的总和）也将更新在给定范围内的最小值，步骤4不再需要。我们可以只比较C [I]闵[I + 1]。这意味着我们只需要单遍输入数组。或者，我们可以这样的算法并不适用于数组，但为数字流。

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.

几个例子：

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

对于多precision输入数字这种方法需要O（N * M）的时间和O（M）的空间。其中M是最大编号的数组在。需要同时只是阅读所有的数字（并且在最坏的情况下，我们需要他们的每一个位）。

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 *日志R），其中R是由这个算法（它实际上，输出敏感的变体）中找到的值。需要这种优化唯一的修改是不是处理整数一次，对它们进行处理位数按位数：第一阶段处理每个数字的低位（如位0..63），第二关 - 下一个位（如64..127）等，我们可以忽略所有高阶位的结果后发现。也这降低空间要求到O（K）的数字，其中K是在机器字位数。

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.

这篇关于不能从数字的总和形成了从阵列最小的数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！