Show problems as
Classic problem #322MediumArrayDynamic ProgrammingBreadth-First SearchKnapsack ProblemComplete Knapsack

Coin Change

Real-world version: Fewest Tokens for the Charge
Tracked in this browser only
Read Coin Change on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstOptimal Substructure · Dynamic Programming, animated step by step

A toll booth accepts plastic tokens. The integer array values lists the token types the booth recognises, where each entry is the credit one token of that type carries, and the booth's dispenser holds an unlimited number of tokens of every listed type.

A driver owes charge credits and the booth gives no change, so the tokens dropped in must add up to charge exactly. Return the smallest number of tokens that does it. If no combination of the listed types adds up to charge, return -1.

A charge of 0 credits is settled by dropping in nothing at all, so the answer there is 0.

Examples

Example 1

Input
values = [1, 4, 6], charge = 8
Output
2

Two 4-credit tokens settle the charge. Reaching for the 6 first would force two 1s after it, which costs three tokens.

Example 2

Input
values = [7, 5], charge = 3
Output
-1

Every token carries more credit than the charge, and the booth gives no change, so the charge cannot be settled.

Example 3

Input
values = [3, 10], charge = 0
Output
0

Nothing is owed, so no token is needed.

Constraints

  • 1 <= values.length <= 12
  • 1 <= values[i] <= 2^31 - 1
  • 0 <= charge <= 10^4
  • Every token type may be used any number of times

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def fewest_tokens(values: list[int], charge: int) -> int:
Java
public int fewestTokens(int[] values, int charge)

More on the same topics