Fewest coins to make an amount

Dynamic programming Mid-level Python 3.13+ Kotlin 2.4+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

What does this print?

Python 3.13

coins, amount = [1, 3, 4], 6
greedy, left = 0, amount
for c in sorted(coins, reverse=True):
    greedy += left // c
    left %= c
print(greedy)

Options326

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 3

Right: greedy takes 4 + 1 + 1, while 3 + 3 needs only two coins.

One counterexample is enough to rule out greedy, which is why the table checks every coin for every amount.

Why not the others?

B 2. That is the true best, which greedy misses.
C 6. Greedy uses the largest coin first, not six ones.

30-second answer

Let need[a] be the fewest coins for amount a, with need[0] = 0. For each a, try every coin c ≤ a: need[a] = min(need[a - c] + 1). Fill a from 1 upward so the smaller amounts are ready. O(amount × coins) time, O(amount) memory. Greedy 'largest coin first' fails for values like [1, 3, 4] and amount 6.

Practise saying it · 45 s. No recording, just a timer

Explain the fewest-coins DP.

Say your answer out loud, then check which of these points you covered:

need[a] = min(need[a - c] + 1)
Fill upward from 0
O(amount × coins)

Deep dive

The 1-D DP over amounts is the template for 'fewest pieces to build a total'.

Use infinity for 'not reachable yet' so min() works without special cases.

BFS over amounts gives the same answer, since every coin adds one step.

Python solution Ran on Python 3.13.5 · mypy --strict

Python 3.13

import math


def fewest_coins(coins: list[int], amount: int) -> int:
    need = [0] + [math.inf] * amount  # need[a]: fewest coins for a
    for total in range(1, amount + 1):  # smaller totals are ready
        for coin in coins:
            if coin <= total and need[total - coin] + 1 < need[total]:
                need[total] = need[total - coin] + 1
    best = need[amount]
    return -1 if best == math.inf else int(best)

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1

Kotlin 2.4

fun fewestCoins(coins: List<Int>, amount: Int): Int {
    val none = Int.MAX_VALUE
    val need = IntArray(amount + 1) { if (it == 0) 0 else none }
    for (total in 1..amount) { // smaller totals are ready
        for (coin in coins) {
            if (coin > total || need[total - coin] == none) continue
            need[total] = minOf(need[total], need[total - coin] + 1)
        }
    }
    return if (need[amount] == none) -1 else need[amount]
}

Common mistakes

Using greedy, which is only correct for some coin systems.
Returning infinity instead of -1.

Senior take & follow-ups

Give the greedy counterexample first; it shows why DP is needed.

Follow-up questions

Think of your answer first, then open the hint.

How do you count the ways instead?
Show hint
Loop coins on the outside and amounts inside, adding ways[a - c]; that counts each combination once.
How do you list the coins used?
Show hint
Store which coin gave each best value and walk back from the amount.

What each operation costs: Two Dimensional Arrays

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.