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

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

Open in the Dojo editor