Patch the Stamp Collection
HardGreedy
Problem
A post office has a sorted list of stamps stamps (values may repeat; each stamp can be used once per parcel). A postage amount is payable if some subset of the stamps adds up to it exactly.
You may print new stamps of any positive value. Return the minimum number of new stamps needed so that every amount from 1 to limit is payable.
Example 1
- Input:
- stamps = [1, 3], limit = 6
- Output:
- 1
With 1 and 3 you can pay 1, 3, 4. Adding a 2 makes 1 through 6 payable.
Example 2
- Input:
- stamps = [1, 5, 10], limit = 20
- Output:
- 2
Add 2 and 4 (1, 2, 4 cover 1–7; with 5 up to 12; with 10 up to 22).
Example 3
- Input:
- stamps = [1, 2, 2], limit = 5
- Output:
- 0
Constraints
- 0 ≤ stamps.length ≤ 1000
- 1 ≤ stamps[i] ≤ 10^4, sorted ascending
- 1 ≤ limit ≤ 2^31 − 1
Hint
Show the first hint
Suppose the stamps so far pay every amount in [1, reach]. What does adding a stamp of value v ≤ reach + 1 do to that range?
Walkthrough
How to approach it
01Clarify before coding
- Can a stamp be used twice in one payment? No, each physical stamp once.
- Are the stamps sorted? Yes, ascending.
- Can limit be huge? Up to 2^31 − 1, so we cannot enumerate amounts.
02Brute force
Try adding 0, 1, 2, … stamps of every possible value and check coverage with subset sums.
Cost: Exponential in the number of added stamps and pseudo-polynomial in limit: impossible.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.