Find minimum sum that cannot be formed

Question

Given positive integers from 1 to N where N can go upto 10^9. Some K integers from these given integers are missing. K can be at max 10^5 elements. I need to find the minimum sum that can't be formed from remaining N-K elements in an efficient way.

Example; say we have N=5 it means we have {1,2,3,4,5} and let K=2 and missing elements are: {3,5} then remaining array is now {1,2,4} the minimum sum that can't be formed from these remaining elements is 8 because :

1=1
2=2
3=1+2
4=4
5=1+4
6=2+4
7=1+2+4

So how to find this un-summable minimum?

I know how to find this if i can store all the remaining elements by this approach:

We can use something similar to Sieve of Eratosthenes, used to find primes. Same idea, but with different rules for a different purpose.

1. Store the numbers from 0 to the sum of all the numbers, and cross off 0.
2. Then take numbers, one at a time, without replacement.
3. When we take the number Y, then cross off every number that is Y plus some previously-crossed off number.
4. When we have done this for every number that is remaining, the smallest un-crossed-off number is our answer.

However, its space requirement is high. Can there be a better and faster way to do this?

Answer 1

Here's an O(sort(K))-time algorithm.

Let 1 &leq; x₁ &leq; x₂ &leq; … &leq; x_m be the integers not missing from the set. For all i from 0 to m, let y_i = x₁ + x₂ + … + x_i be the partial sum of the first i terms. If it exists, let j be the least index such that y_j + 1 < x_j+1; otherwise, let j = m. It is possible to show via induction that the minimum sum that cannot be made is y_j + 1 (the hypothesis is that, for all i from 0 to j, the numbers x₁, x₂, …, x_i can make all of the sums from 0 to y_i and no others).

To handle the fact that the missing numbers are specified, there is an optimization that handles several consecutive numbers in constant time. I'll leave it as an exercise.