The minimum amount that cannot be obtained from the set

Question

Given the set S of natural numbers whose elements do not have to be different, I need to find the minimum non-negative sum that cannot be obtained from any subset of this set.

Example: if S = {1, 1, 3, 7} , we can get 0 as (S' = {}) , 1 as (S' = {1}) , 2 as (S' = {1, 1}) , 3 as (S' = {3}) , 4 as (S' = {1, 3}) , 5 as (S' = {1, 1, 3}) , but we cannot get 6 .

Now we are given one array A , consisting of N positive integers. Their queries M , each of which consists of two integers Li and Ri , describe the i-th query: we need to find this Sum, which cannot be obtained from the array elements ={A[Li], A[Li+1], ..., A[Ri-1], A[Ri]} .

I know, to find it using the brute force approach, which must be done in O (2 ^ n). But under the condition 1 ≤ N, M ≤ 100,000 . This is impossible to do. So their effective approach to this.

Answer 1

Concept

Suppose we had a bool array representing which numbers have not yet been found (by summing).

For each number n we meet in an ordered (increasing value) subset of S , we do the following:

• For each existing True value in position i in numbers we set numbers[i + n] to True
• Set numbers[n] to True

With the help of such a sieve, we mark all the numbers found as True and iterate over the array when the algorithm completes, we find the minimum unattainable amount.

---

Completion

Obviously, we cannot have such a solution, because the array must be infinite in order to work for all sets of numbers.

The concept can be improved by making a few comments. When you enter 1, 1, 3 array becomes (sequentially):

^{(numbers represent True values)}

An important point to make:

• (3) For each next number, if previous numbers have already been found, it will be added to all these numbers. This means that if there were no spaces before the number, there will be no spaces after this number .

For the next input 7 it can be argued that:

• (4) Since the input order is ordered, the number will not be less than 7
• (5) If the numbers are not less than 7 , then 6 cannot be obtained

We can conclude that:

• (6) the first gap is the minimum unattainable number .

---

Algorithm

Due to (3) and (6), we actually do not need the numbers array, we only need one value, max - is the maximum number found so far .

Thus, if the next number n greater than max + 1 , then a space will be made, and max + 1 is the minimum unattainable number.

Otherwise, max becomes max + n . If we skipped all S , the result would be max + 1 .

Actual code (C # easily converted to C):

 static int Calculate(int[] S) { int max = 0; for (int i = 0; i < S.Length; i++) { if (S[i] <= max + 1) max = max + S[i]; else return max + 1; } return max + 1; } 

It should run pretty fast, since this is obviously linear time (O (n)). Since the input to the function must be sorted, with quick sort it will be O (nlogn). I managed to get the results M = N = 100000 on 8 cores in just 5 minutes.

With the upper limit of the number 10 ^ 9, you can use the radix sort to approximate the O (n) time for sorting, however this will still be more than 2 seconds due to the large number of required types.

But we can use the statistical probability of 1 random to eliminate the subsets before sorting. First check if 1 exists in S , if not, then each query result is 1, because it cannot be received.

Statistically, if we randomly out of 10 ^ 9 numbers 10 ^ 5 times, we have a 99.9% chance of not getting a single one.

Before each sort, check to see if it contains a subset of 1; if not, then its result is one.

With this modification, the code runs on 2 milliseconds on my machine. Here is the code at http://pastebin.com/rF6VddTx

Answer 2

This is a variation of the problem of the subset of sums , which is NP-Complete , but there is a pseudopolynomial Dynamic Programming solution that you can use here, based on a recursive formula:

 f(S,i) = f(S-arr[i],i-1) OR f(S,i-1) f(-n,i) = false f(_,-n) = false f(0,i) = true 

A recursive formula is basically an exhaustive search, each amount can be achieved if you can get it using the i element OR without the i element.

Dynamic programming is achieved by constructing a table SUM+1 x n+1 (where SUM is the sum of all elements and n is the number of elements) and construction from the bottom up.

Sort of:

 table <- SUM+1 x n+1 table //init: for each i from 0 to SUM+1: table[0][i] = true for each j from 1 to n: table[j][0] = false //fill the table: for each i from 1 to SUM+1: for each j from 1 to n+1: if i < arr[j]: table[i][j] = table[i][j-1] else: table[i][j] = table[i-arr[j]][j-1] OR table[i][j-1] 

Once you have a table, you will need the smallest i such that for all j : table[i][j] = false

The complexity of the solution is O(n*SUM) , where SUM is the sum of all elements, but note that the algorithm can actually be truncated after the required number has been found, without having to continue the following lines, which are not needed for the solution.