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$
  • 1
    $\begingroup$ What is the point of taking the complement rather than using $A$ directly in the place of $C$? $\endgroup$ – Tom van der Zanden Jan 5 '15 at 14:00
  • $\begingroup$ @TomvanderZanden It affects the input size. $\endgroup$ – Yuval Filmus Jan 5 '15 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 '15 at 5:52
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$
  • $\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 '15 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$ – Yuval Filmus Jan 6 '15 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 '15 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 '15 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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