Fewest coins that cover every amount up to a limit

Think of the coins you pick as a multiset. A multiset "covers" [1, max] when every amount in that range is the sum of some sub-multiset. Each denomination can be picked any number of times; we minimise the total number of coins picked.

Brute force. Try multisets of size 0, 1, 2, ... and check each one with a subset-sum bitmask (mask |= mask << c). This is exponential, but it is the right thing to state first and it makes a good test oracle.

Key observation (the reach invariant). Sort the picked coins ascending and let reach be their running sum. If every amount in [0, reach] can be formed, then adding a coin c keeps the range gap-free exactly when c <= reach + 1. The new range is [0, reach + c]. If c > reach + 1, the amount reach + 1 can never be formed by these coins or any larger coin picked later. So every valid answer, read in sorted order, follows c_i <= (c_1 + ... + c_{i-1}) + 1. The first coin must be 1. If 1 is not a denomination, return -1.

Greedy. Start with reach = 0 and repeat: take the largest denomination d <= reach + 1, then set reach += d. Stop once reach >= max.

Why largest is optimal: by induction, after k picks the greedy reach is at least the reach of any valid sequence of k coins. Suppose another sequence has reach r' <= r after k coins. Its next coin is at most r' + 1 <= r + 1, so the greedy can pick that same coin or a larger one, and its reach stays ahead. So the greedy passes max in the fewest picks. This is the same argument as LeetCode 330 (Patching Array), but here we can only "patch" with the given denominations.

Batching. With a huge max (say 10^18) and a denomination set like [1], picking one coin at a time is too slow. Notice that the greedy keeps choosing the same d until reach + 1 reaches the next denomination nxt, or until reach >= max. So we jump in one step: goal = min(max, nxt - 1) and k = ceil((goal - reach) / d). Each denomination is the "current" one in at most one batch, so the loop runs at most n times.

Invariants:

• Every amount in [0, reach] is formable from the coins counted so far.
• count is the fewest coins that reach reach or beyond.

from bisect import bisect_right


def min_coins_to_cover(denominations: list[int], max_amount: int) -> int:
    """Fewest coins (unlimited supply of each denomination) whose subset
    sums cover every amount in [1, max_amount]. -1 if impossible."""
    if max_amount <= 0:
        return 0
    coins = sorted({d for d in denominations if d > 0})
    if not coins or coins[0] != 1:
        return -1                      # amount 1 can never be formed

    reach = 0                          # invariant: every amount in [0, reach] is formable
    count = 0
    while reach < max_amount:
        # Largest denomination that does not open a gap: d <= reach + 1.
        i = bisect_right(coins, reach + 1) - 1
        d = coins[i]
        # Keep taking d until the next denomination becomes usable
        # (reach + 1 >= next) or we are done, in one arithmetic step.
        nxt = coins[i + 1] if i + 1 < len(coins) else None
        goal = max_amount if nxt is None else min(max_amount, nxt - 1)
        k = -(-(goal - reach) // d)    # ceil division, k >= 1
        reach += k * d
        count += k
    return count


def min_coins_brute(denominations: list[int], max_amount: int) -> int:
    """Oracle: try every multiset of size 0, 1, 2, ... and check coverage."""
    from itertools import combinations_with_replacement
    coins = sorted({d for d in denominations if d > 0})
    if max_amount <= 0:
        return 0
    if 1 not in coins:
        return -1
    full = (1 << (max_amount + 1)) - 1
    for k in range(max_amount + 1):
        for combo in combinations_with_replacement(coins, k):
            mask = 1
            for c in combo:
                mask |= mask << c
            if mask & full == full:
                return k
    return -1


if __name__ == "__main__":
    import random

    assert min_coins_to_cover([1, 2, 5], 10) == 4      # 1, 2, 2, 5
    assert min_coins_to_cover([1, 5, 10], 27) == 7     # 1, 1, 1, 1, 5, 10, 10
    assert min_coins_to_cover([1, 3], 10) == 5         # 1, 1, 3, 3, 3 (sum 11)
    assert min_coins_to_cover([2, 5], 10) == -1
    assert min_coins_to_cover([1], 10**18) == 10**18
    assert min_coins_to_cover([4, 1, 1], 0) == 0
    for _ in range(2000):
        ds = random.sample(range(1, 12), random.randint(1, 4))
        m = random.randint(0, 14)
        assert min_coins_to_cover(ds, m) == min_coins_brute(ds, m), (ds, m)
    print("all tests pass")

• Sorting and deduplicating: O(n log n) time, O(n) space.
• Greedy loop: each iteration either ends the loop or moves reach + 1 past the next denomination, so there are at most n iterations. Each one costs O(log n) for the binary search, so the loop is O(n log n). The running time does not depend on max. (A plain "one coin per step" loop would be O(answer), which is up to max.)
• Extra space beyond the sorted array: O(1).
• Brute force: exponential. Use it only as a test oracle.

• [1, 2, 5], max = 10 → 4 (1, 2, 2, 5: reach goes 1, 3, 5, 10).
• [1, 5, 10], max = 27 → 7 (four 1s reach 4, a 5 reaches 9, two 10s reach 29).
• [1, 3], max = 10 → 5 (1, 1, 3, 3, 3).
• [1], max = 6 → 6.
• [2, 5], max = 10 → -1 (no 1, so the amount 1 is impossible).
• [], max = 3 → -1.
• [3, 1, 1, 3], max = 4 → 3 (duplicates are ignored; 1, 1, 3 is needed because 1 and 3 alone miss 2).
• [1, 100], max = 50 → 50 (100 is never usable before the range is already covered).
• [1, 2, 4, 8], max = 15 → 4 (powers of two, each coin doubles the range).
• max = 0 → 0 for any input.
• [1], max = 10^18 → 10^18 in one batched step (checks there is no per-coin loop).

1. Return the coins, not only the count. Record (d, k) for each batch. That is a compact run-length answer. Expanding it to a full list costs O(answer), so ask whether the compact form is acceptable.
2. Limited supply (each denomination has a count cnt[d]). The greedy still works: take the largest d <= reach + 1 that still has coins left. Batch by taking min(k, cnt[d]). When d runs out, fall back to the next smaller denomination that still has coins. If nothing <= reach + 1 is left, return -1. A max-heap or a pointer over the sorted denominations keeps this near O(n log n).
3. You already own some coins (LeetCode 2952 / 330 style). Seed reach by sweeping your owned coins in sorted order while owned <= reach + 1. When the next owned coin is too large, buy coins with the greedy until reach + 1 >= owned, then absorb it. Count only bought coins. With unrestricted denominations, the best coin to buy is always reach + 1.
4. Many queries for different max values. Run the greedy once up to the largest query and store the batch boundaries (reach_after_batch, count_after_batch, d) in a list. For a query m, binary-search the batch where reach first reaches m, then compute the partial k with the same ceil formula. That gives O(log n) per query.
5. Every amount must use at most t coins, or exact change for a single amount. These are different problems. Exact change for one amount is the classic coin-change DP in O(n * amount). Say so instead of forcing the greedy onto it.

Mid-level (L4)

• Clarify that supply is unlimited, that coins are a multiset, and that -1 means 1 is missing.
• Find the reach invariant (c <= reach + 1) and code the one-coin-at-a-time greedy correctly.
• Walk through a small example by hand and cover max = 0, no 1, and duplicates.

Senior (L5)

• Justify "take the largest usable denomination" with the stays-ahead exchange argument, not just intuition.
• Notice the O(max) loop is too slow for large max, and batch with a ceil division so the time is O(n log n).
• Test against a brute-force oracle on small random inputs, and handle overflow and ceil off-by-ones.

Staff (L6+)

• Link it to Patching Array and explain what changes when coins are limited or partly owned.
• Design the multi-query version (precomputed batch boundaries plus binary search) and the run-length output format.
• Clearly separate this covering problem from exact-change DP, and discuss when greedy fails (for example, with an "every amount using at most t coins" constraint).