0752HardArrayGreedy

Minting Tokens To Cover Every Toll

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A toll plaza settles charges from a tray of tokens. values lists the face values of the tokens in the tray in non-decreasing order, and each token in the tray may be handed over at most once. Two tokens may carry the same face value, and each of them still counts as its own token.

An amount is settleable when some collection of the tokens on hand adds up to exactly that amount.

The plaza must be able to settle every amount from 1 to limit inclusive. To get there you may mint extra tokens: each minted token carries any positive integer face value you choose, you may mint several tokens carrying the same face value, and minted tokens join the tray and are also usable at most once each.

Return the smallest number of tokens you have to mint.

limit reaches 2^31 - 1, so a solution that walks through the amounts one at a time, or that builds anything sized by limit, will not finish.

Examples

Example 1

Input: values = [1, 2, 20], limit = 40
Output: 3

Mint tokens of 4, 8 and 16. The tray then holds 1, 2, 4, 8, 16 and 20. Every amount from 1 to 31 is a sum of some of 1, 2, 4, 8 and 16, and every amount from 32 to 40 is the 20 plus an amount from 12 to 20, which those same five tokens supply.

Example 2

Input: values = [1, 2, 4, 8, 16], limit = 31
Output: 0

Each amount from 1 to 31 is already a sum of some of the five tokens on hand, so nothing has to be minted.

Example 3

Input: values = [7, 9], limit = 6
Output: 3

The tray cannot settle 1, 2 or 3, since its smallest token is 7. Minting 1, 2 and 4 leaves the tray holding 1, 2, 4, 7 and 9, and 1, 2, 1 + 2, 4, 1 + 4 and 2 + 4 settle the amounts 1 through 6.

Constraints

1 <= values.length <= 1000
1 <= values[i] <= 10^4
1 <= limit <= 2^31 - 1
values is given in non-decreasing order.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_tokens_to_mint(values: list[int], limit: int) -> int:

Java

public int minTokensToMint(int[] values, int limit)

The intended approach

Time O(m + log limit) for a tray of m tokens: each token is examined once and each minted token at least doubles the run.Space O(1).

Carry one number: the largest `covered` such that every amount from `1` to `covered` is already settleable. Adding a token of face value `v` to a tray that settles `1..covered` extends the run to `covered + v`, but only while `v` is at most `covered + 1`; a larger face value leaves `covered + 1` unsettleable and the run stops growing. So walk the tray in order: whenever the next token's face value fits under `covered + 1`, absorb it and grow `covered` by that value. When it does not fit, or the tray is spent, mint one token and absorb it, taking the largest face value still allowed, which is `covered + 1` and pushes the run to `2 * covered + 1`. Stop once `covered` reaches `limit`. Every intermediate value of `covered` stays below `2 * limit`, so nothing overflows a 64-bit or double-precision range, and no structure sized by `limit` is ever built.

Pythonentry point: min_tokens_to_mint

def min_tokens_to_mint(values, limit):
    # Track the largest prefix of amounts that is fully payable. A token may be
    # taken into the prefix only when its face value does not skip past the
    # first unpayable amount.
    # O(m + log limit) time, O(1) space. The running prefix never passes
    # 2 * limit, so it stays well inside 2^53.
    covered = 0
    minted = 0
    i = 0
    m = len(values)
    while covered < limit:
        if i < m and values[i] <= covered + 1:
            covered += values[i]
            i += 1
        else:
            minted += 1
            covered += covered + 1
    return minted

The obvious version

Search over the minted tokens directly. For k = 0, 1, 2 and so on, try every multiset of k face values taken from 1 to limit and test whether the whole tray then settles every amount, using a bitmask of reachable subset sums. Assumes nothing about which face values are worth minting, and only runs for a tiny limit.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_tokens_to_mint(values, limit):
    """Search over the extra tokens themselves. For k = 0, 1, 2, ... try every
    multiset of k face values drawn from 1..limit and test payability with a
    subset-sum bitmask. Assumes nothing about which face values are worth
    minting, and is only usable for a small limit."""
    from itertools import combinations_with_replacement

    full = (1 << limit) - 1

    def reachable(extra):
        mask = 1
        for v in list(values) + list(extra):
            if v <= limit:
                mask |= mask << v
        return ((mask >> 1) & full) == full

    if reachable(()):
        return 0
    pool = list(range(1, limit + 1))
    k = 1
    while True:
        for extra in combinations_with_replacement(pool, k):
            if reachable(extra):
                return k
        k += 1

How this problem was checked

Reference solution executed against 16 test cases — 16 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in