0838MediumArrayDynamic Programming

Recover the Coin Denominations

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 mint used a set of coin face values, all distinct positive whole numbers. For an amount a, the number of ways to make a is the number of different multisets of those coins that total exactly a, so order never matters and a face value may be reused freely.

You are given numWays, where numWays[i] is the number of ways to make the amount i + 1. Every face value the mint used is at most numWays.length.

Return the face values the mint used, in increasing order. If no set of face values produces exactly these counts, return an empty list.

Examples

Example 1

Input: numWays = [0, 1, 0, 1, 0]
Output: [2]

With a single face value of 2 the amounts 2 and 4 can each be made one way, using one coin and two coins, while the amounts 1, 3 and 5 cannot be made at all.

Example 2

Input: numWays = [1, 1, 1, 1]
Output: [1]

With a single face value of 1 each of the amounts 1 through 4 can be made exactly one way, by repeating that coin.

Example 3

Input: numWays = [2]
Output: []

The amount 1 can only ever be made by a single coin of face value 1, so it can never be made two ways and no set of face values fits.

Constraints

1 <= numWays.length <= 100
0 <= numWays[i] <= 2 * 10^8

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 recover_denominations(numWays: list[int]) -> list[int]:

Java

public List<Integer> recoverDenominations(int[] numWays)

The intended approach

Time O(L^2) for a list of length L: adding a face value sweeps the table once.Space O(L) for the way-count table.

Build up the way-count table for the face values decided so far, sweeping amounts upwards when a face value is added so that the face value may be reused. Walk the amounts in increasing order: the ways to make amount `v` using only face values below `v` are already settled, so comparing that count with the wanted one decides whether `v` itself was minted. It can only ever be short by exactly one, the single-coin way, so any other gap makes the list impossible. Finish by checking the completed table against every wanted count, which rejects lists that no set of face values can produce.

Pythonentry point: recover_denominations

def recover_denominations(numWays):
    top = len(numWays)
    # ways[amount] counts the multisets of the coins found so far; adding a coin
    # of face value v is one in-place sweep of that table
    ways = [0] * (top + 1)
    ways[0] = 1
    found = []
    for value in range(1, top + 1):
        want = numWays[value - 1]
        if ways[value] == want:
            continue
        if ways[value] + 1 != want:
            return []
        found.append(value)
        for amount in range(value, top + 1):
            ways[amount] += ways[amount - value]
        if ways[value] != want:
            return []
    for value in range(1, top + 1):
        if ways[value] != numWays[value - 1]:
            return []
    return found

The obvious version

Try every set of candidate face values, smallest sets first, build the way-count table from scratch for each and compare it with the wanted counts. Exponential in the list length, but it assumes nothing about which face values must be present.

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_recover_denominations(numWays):
    top = len(numWays)

    def tally(coins):
        table = [0] * (top + 1)
        table[0] = 1
        for coin in coins:
            for amount in range(coin, top + 1):
                table[amount] += table[amount - coin]
        return table[1:]

    # try every set of face values from 1..top, smallest sets first
    import itertools
    for size in range(0, top + 1):
        for combo in itertools.combinations(range(1, top + 1), size):
            if tally(list(combo)) == numWays:
                return list(combo)
    return []

How this problem was checked

Reference solution executed against 12 test cases — 12 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