dsa · hard
Top Up the Coin Rack
A vending rack is stocked with coins, a sorted list of distinct denominations, and must be able to make **every** total from 1 to n as a sum of available denominations, each denomination used **at most once** per total. Before use you may add plain unit top-ups of any positive amount; each top-up is one new denomination and you want as few as possible.
Arguments
coins— the stocked denominations, strictly increasingn— the largest total that must be reachable
Return the minimum number of top-ups needed so every total in [1, n] is reachable.
Example
coins = [1,3], n = 6
With 1 stocked, coverage is 1..1. The next stocked coin 3 needs coverage to reach 2 first, so a top-up of 2 is added: coverage becomes 1..3. Now 3 ≤ 3 + 1, so the stocked coin extends coverage to 1..6 — every total up to 6 is reachable. Answer 1 top-up (the denomination 2).
coins = [1,5,10], n = 20 → coverage 1..1, 5 is too big → top-up 2 (covers 1..3), 5 still too big → top-up 4 (covers 1..7), then 5 and 10 extend coverage past 20. Answer 2.
Constraints
0 <= coins.length <= 4*10^4 1 <= n <= 2 * 10^9 1 <= coins[i] <= 2 * 10^9 coins is sorted in strictly increasing order Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.
Examples
Example 1
Input: [1,3] 6 Expected: 1
Example 2
Input: [1,5,10] 20 Expected: 2
Example 3
Input: [1,2,4] 10 Expected: 1