1
$\begingroup$

Given a number N, and some set $A=\{a, 1\le a\le N\}$, and let $B=\{\text{every integer} \in [1,N]\}$, and $C=B\setminus A$ (Set C has all values from B not in A)

What is the best way of finding the smallest number ($S$) that can't be obtained from the sum of any subset of C?

i.e.
if $A=\emptyset$, the smallest number $S= 1+\sum_1^Nx$,
but if $A\ne \emptyset,\ S\leq 1+ \sum_1^Nx-\sum_{i=0}^na_i$,
However if $N=10,A=\{2\}$, then $S=2$, and that is something that I'm not sure how to get efficiently.

I can obviously bruteforce the solution, but I can't find a better way, and I don't know how these kinds of problems are called so that I could Google them.

$\endgroup$
3
  • 1
    $\begingroup$ What is the point of taking the complement rather than using $A$ directly in the place of $C$? $\endgroup$ Jan 5, 2015 at 14:00
  • $\begingroup$ @TomvanderZanden It affects the input size. $\endgroup$ Jan 5, 2015 at 14:42
  • $\begingroup$ @TomvanderZanden, it's a constraint part of the problem, where the sum if 1 to N must exclude any number in that set. But if there is a way to solve it using A, That would be ok as well. $\endgroup$
    – Goodwine
    Jan 6, 2015 at 5:52

1 Answer 1

2
$\begingroup$

One possible way is computing the product $$ \prod_{a \in C} (1+x^a). $$ This is a polynomial $p(x)$. The coefficient of $x^j$ will be non-zero if and only if $j$ can be represented as the sum of some subset of $C$. Therefore, given $p(x)$, you can read off the set of all numbers that are obtainable as the sum of some subset, and then find the smallest that isn't obtainable (i.e., the smallest integer $j$ such that $x^j$ has coefficient $0$ in $p(x)$).

As a bonus, you'll also get the number of possible representations of each number which is representable.

The running time is polynomial in $N$, and doubtless you can optimize the degree of the polynomial. (This is dynamic programming in disguise.)

If you're after an algorithm polynomial in the input length (the input can be either $A$ or $C$), that's a different question. The problem is that the input can be very small; though perhaps such inputs can be handled separately.

$\endgroup$
4
  • $\begingroup$ Is there a name for these kinds of problems? or is it an adhoc dp solution? I mean, the formula makes it look like a well know problem, and I don't know it's name :( $\endgroup$
    – Goodwine
    Jan 6, 2015 at 5:54
  • 1
    $\begingroup$ @D.W. It gives you all numbers that can be obtained as a sum of a subset of $C$, along with the number of different such representations. You then look for the smallest number that has no representations. $\endgroup$ Jan 6, 2015 at 9:02
  • 1
    $\begingroup$ This method is exactly the same as the pseudo-polynomial DP for subset sum problem, see en.wikipedia.org/wiki/Subset_sum_problem It is not polynomial since an instance only consists of $A$ and $N$. $\endgroup$
    – Bangye
    Jan 6, 2015 at 19:22
  • $\begingroup$ By playing around with the product, I got to a hypothesis where we will define that for 2 sets of consecutive numbers $X=\{[1,k]\}, Y=\{[k+l,m]\}$, $X$ "chains" $Y$ if $\sum_{x\in X} x >= k+l-1$. And "chains" means that any number $\in [i,m]$ can be formed from the sum of at least one non empty subset of $X\cup Y$, and if it doesn't "chain", the smallest number possible not formed by a subset of $C$ is the $(\sum_{x\in X} x) + 1$. If $X$ "chains" $Y$, then $X\cup Y$ "chains" $Z:\{\text{next set of consecutive numbers}\}$ if the same condition holds for these new sets. $\endgroup$
    – Goodwine
    Jan 7, 2015 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.