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?

Angieangil

I don't know, but a quick and dirty initial check is obviously: if '1' missing, return '1'; if '2' missing, return '2'; – Homestead

This is a problem from an active contest: codechef.com/JAN15/problems/CLPERM – Linis

This question appears to be off-topic because it is cheating at an active contest: codechef.com/JAN15/problems/CLPERM – Bulbous

Answer 1

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

Let 1 ≤ x₁ ≤ x₂ ≤ … ≤ 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.

Linis

Answer 2

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

This will set a '1' for every value you can make.

Running time is linear in N, and bitvector operations are fast.

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

First number you can't make is 8.

Crossarm

Please provide some pseudocode.Am not getting what you are trying to say.As what is X , Ni is hard to understand without some pseudocode – Angieangil

Still not getting what you are trying – Angieangil

I'm suggesting using bitwise operations. Also, are you sure linear is too slow? How fast do you need this to be? – Crossarm

@DalveGalvin O(KlogK) at max.And yes linear in N is slow in this case.Also am not getting your approach are you just taking bitvector in place of array to store the elements ? – Angieangil

@Angieangil How fast do you think your sieve method is? – Crossarm

I don't know exactly but for large N it take huge time.Can you post a function or so to clearify your approach.Because i think your approach is not linear but better than that.So perhaps it may work – Angieangil

@Angieangil My approach is linear. Just loop through the numbers in N-K and apply the bitvector ops. – Crossarm

Then it wont work.Because we need not loop over all the elements as you can see we are provided 1 to N elements.So we can take this advantage – Angieangil

How to store 10^9 elements is issue. – Angieangil

You don't need to. Just store the ones you're skipping – Crossarm

Store your K elements in a hash. Loop from 1 to N, and skip processing when you get to an element in K. – Crossarm

Answer 3

Here is my O(K lg K) approach. I didn't test it very much because of lazy-overflow, sorry about that. If it 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: well, thanks God @DavidEisenstat in his answer wrote the description of the approach I used, so I don't have to write it. Basically, what he mentions as exercise is not adding the "existing numbers" one by one, but all at the same time. Before this,you just need to check if some of them breaks the invariant, which can be done using binary search. Hope it helped.

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

Gena

:) you are so damn right. I'm really dumb these days. I will edit the code. Thanks. – Gena

See the edit: the code was updated. As I said, I didn't check it. If this is a problem from some programming contest or some online judge, post also the reference. Now the answer for that case is 29, but I don't know if it's the correct one. – Gena

10^9 can fit int 32 bits (even 31), so any (signed) 32-bit integer type will do (no need for long long types) – Steady

10^9 can fit in 32-bit, but the answer to the problem may not. – Gena