Find the minimum amount that cannot be formed

Question

Given positive integers from 1 to N, where N can go up to 10 ^ 9 . Some K integers from these given integers are missing. K can be no more than 10 ^ 5 elements . I need to find the minimum amount that cannot be formed from the remaining NK elements in an effective way.

Example; let's say we have N = 5, which means we have {1,2,3,4,5}, and K = 2 and the missing elements: {3,5}, then the remaining array is now {1,2,4} the minimum amount , which cannot 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 do you find this non-cumulative minimum?

I know how to find this if I can save all other elements using this approach:

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

• Keep numbers from 0 to the sum of all numbers and reset 0.
• Then do the numbers, one at a time, without replacement.
• When we take the number Y, we discard each number equal to Y plus some previously crossed number.
• When we did this for each remaining number, the smallest number without interception is our answer.

However, his need for space is high. Could there be a better and faster way to do this?

Answer 1

The O (sort (K)) time algorithm is used here.

Let 1? x ₁ ? x ₂ ? & Hellip; & Leq; x _m are integers not in the set. For all I from 0 to m, let y _i = x ₁ + x ₂ + & hellip; + x _i is a partial sum of the first i members. If it exists, let j be the smallest index such that y _j + 1 <x <sub> J + 1sub>; otherwise, let j = m. By induction, it can be shown 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 ₂ , & hellip ;, x _i can do everything amounts from 0 to y _i and no other).

To cope with the fact that missing numbers are indicated, there is an optimization that processes several consecutive numbers in constant time. I will leave it as an exercise.

Answer 2

Let X be a bitvector initialized to zero. For each number Ni you set X = (X | X <Ni) | Government insurance (i.e. you can make Ni, and you can increase any value you could make earlier Ni).

For each value you can make, it will be set to "1".

The runtime is linear in N, and the bitvector operations are fast.

 process 1: X = 00000001 process 2: X = (00000001 | 00000001 << 2) | (00000010) = 00000111 process 4: X = (00000111 | 00000111 << 4) | (00001000) = 01111111 

The first number you cannot do is 8.

Answer 3

Here is my approach O (K lg K). I have not experienced this very much due to lazy overflow, sorry. If this works for you, I can explain the idea:

 const int MAXK = 100003; int n, k; int a[MAXK]; long long sum(long long a, long long b) { // sum of elements from a to b return max(0ll, b * (b + 1) / 2 - a * (a - 1) / 2); } void answer(long long ans) { cout << ans << endl; exit(0); } int main() { cin >> n >> k; for (int i = 1; i <= k; ++i) { cin >> a[i]; } a[0] = 0; a[k+1] = n+1; sort(a, a+k+2); long long ans = 0; for (int i = 1; i <= k+1; ++i) { // interval of existing numbers [lo, hi] int lo = a[i-1] + 1; int hi = a[i] - 1; if (lo <= hi && lo > ans + 1) break; ans += sum(lo, hi); } answer(ans + 1); } 

EDIT : ok, thanks God @DavidEisenstat in his answer wrote a description of the approach used, so I do not need to write it. Basically, what he mentions as an exercise does not add the “existing numbers” one by one, but all at the same time. Before that, you just need to check if some of them violate the invariant that can be performed using binary search. Hope this helps.

EDIT2 : as @DavidEisenstat pointed out in the comments, a binary search is not needed, since only the first number in each interval of existing numbers can break the invariant. The code is changed accordingly.