Smallest number that can not be formed from sum of numbers from array

Question

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

But this was nlog(n) solution.

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

Answer 1

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.

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.

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

• 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 less than or equal to 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.

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:

• A[1] = 1, candidate = 1:
  • A[1] ≤ candidate, so set candidate = candidate + A[1] = 2
• A[2] = 2, candidate = 2:
  • A[2] ≤ candidate, so set candidate = candidate + A[2] = 4
• A[3] = 3, candidate = 4:
  • A[3] ≤ candidate, so set candidate = candidate + A[3] = 7
• A[4] = 4, candidate = 7:
  • A[4] ≤ candidate, so set candidate = candidate + A[4] = 11
• A[5] = 13, candidate = 11:
  • A[4] > candidate, so return candidate (11).

So the answer is 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.

Hope this helps!

Answer 2

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

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

1. b=0
2. process 4: b = b | b<<4 | 1000 = 1000
3. process 13: b = b | b<<13 | 1000000000000 = 10001000000001000
4. process 2: b = b | b<<2 | 10 = 1010101000000101010
5. process 3: b = b | b<<3 | 100 = 1011111101000101111110
6. process 1: b = b | b<<1 | 1 = 11111111111001111111111

First zero: position 11.