501. How Many Amounts Cannot Be Made
Coins of m denominations are available in UNLIMITED supply. Count how many of the
amounts 1, 2, ..., n cannot be made.
coins 2 5, n = 11 -> 2 only 1 and 3 cannot be made
coins 3, n = 10 -> 7 only 3, 6 and 9 can be made
Problem 487 asks the smallest unmakeable amount with each coin usable ONCE, and the answer there is a sorted greedy with no table. This one has unlimited supply and asks for a count over a range, and here the table is the right tool.
Worth contrasting deliberately: the two problems differ in one word of the statement and in almost everything about the solution.
## Reachability, unlimited supply
reach[0] = true
for each denomination c:
for v from c up to n: FORWARD
reach[v] = reach[v] or reach[v - c]
answer = how many of 1..n are false
The inner loop runs FORWARD, which is what gives unlimited supply: reach[v - c] may
itself already have been set using c, so c is reused freely.
Run it backward and each coin is available once, which answers a different question
entirely: coins 3, n = 10 would then report 9 unmakeable instead of 7.
## Why the coin loop may be outermost here
For a COUNT of ways the loop order matters enormously, as problem 482 shows. For REACHABILITY it does not: OR is idempotent as well as commutative, so a total reachable by some multiset is found regardless of the order the denominations are processed in.
Knowing that the order is free here, and why, saves worrying about it. The direction of the inner loop is still load-bearing.
## Boundaries
coins 1, n = 5 answers 0. With a 1 available every amount is makeable, which is the
sanity check that nothing is off by one at the top of the range.
coins 4, n = 3 answers 3: the smallest coin exceeds the whole range, so nothing is
makeable. And coins 2, n = 1 answers 1, the smallest such case.
coins 6 9 20, n = 30 answers 18, and it is here because the reachable set is irregular:
6, 9, 12, 15, 18, 20, 21, 24, 26, 27, 29, 30 are makeable and there is no pattern to
shortcut.
reach[0] must be true and amount 0 must NOT be counted, since the range starts at 1.
That is the off-by-one to watch.
## Cost
Time O(m n). Space O(n).
Constraints - `1 ≤ m ≤ 50` - `1 ≤ n ≤ 100000` - `1 ≤ denomination ≤ 100000`
Input
The first line contains two integers m and n.
The second line contains m space-separated denominations.
Output
Print how many of the amounts 1 through n cannot be made.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.