Introduction

Every time a cashier hands you change, they solve a small puzzle: which coins add up to the amount owed, using as few coins as possible?

For the everyday euro or dollar, this feels effortless — you just grab the biggest coin that fits, then the next, and so on. But that easy feeling is misleading. The "fewest coins" question is a genuine optimization problem, and once the coin denominations stop being friendly, the obvious strategy can quietly give you the wrong answer.

In this article we'll start with the intuitive method, watch it fail on a simple example, and discover that the general version of "make change with the fewest coins" is one of those deceptively simple problems that sit right at the edge of what computers can solve efficiently.

The Greedy Approach

The natural strategy is greedy: always take the largest coin that does not exceed what's left to pay, then repeat.

Say you owe 87 cents with coins of 25, 10, 5, and 1:

  • Take 25 → 62 left
  • Take 25 → 37 left
  • Take 25 → 12 left
  • Take 10 → 2 left
  • Take 1, 1 → done

That's 6 coins, and for this coin system it's also the best possible. Currencies like the euro and the US dollar are canonical: they are deliberately designed so that the greedy method always returns the optimal answer. That's exactly why making change feels so easy in real life — the system is rigged in greedy's favour.

The trap is to assume this always holds.

When Greedy Fails

Change the coins to {1, 3, 4} and ask for 6:

  • Greedy takes 4, then 1, then 1 → 3 coins.
  • Optimal is 3 + 3 → 2 coins.

Greedy lost. By committing to the biggest coin too early, it painted itself into a corner. The only way to be sure you've used the fewest coins is to consider combinations that don't start with the largest denomination — and there can be a huge number of those.

The method that always gets it right is dynamic programming: build up the best answer for every amount from 0 up to the target, reusing smaller answers. It's correct for any coin system, at the cost of doing more work.

Try it live: pick a coin set and an amount, and compare what greedy gives against the true optimum.

<div class="row">
  <label>Coins (comma-separated)
    <input id="coins" value="1, 3, 4" spellcheck="false">
  </label>
  <label>Amount
    <input id="amount" type="number" min="0" value="6">
  </label>
</div>
<p id="err" class="err"></p>
<div class="cards">
  <div class="card greedy">
    <h4>Greedy <span class="tag">largest coin first</span></h4>
    <div class="count" id="gCount">–</div>
    <div class="mono" id="gBreak"></div>
  </div>
  <div class="card optimal">
    <h4>Optimal <span class="tag">dynamic programming</span></h4>
    <div class="count" id="oCount">–</div>
    <div class="mono" id="oBreak"></div>
  </div>
</div>
<p id="verdict" class="verdict"></p>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.row { display: flex; gap: 1rem; flex-wrap: wrap; align-items: end; margin-bottom: .5rem; }
label { font-weight: 600; font-size: .9rem; display: flex; flex-direction: column; gap: .2rem; }
input { font: 14px ui-monospace, monospace; padding: .35rem .5rem; border: 1px solid #bbb; border-radius: 6px; }
input#coins { min-width: 12rem; }
.err { color: #b00; font-size: .85rem; min-height: 1em; margin: .1rem 0; }
.cards { display: grid; grid-template-columns: 1fr 1fr; gap: .75rem; margin: .25rem 0; }
.card { border: 1px solid #ddd; border-radius: 10px; padding: .6rem .8rem; }
.card h4 { margin: 0 0 .3rem; font-size: .95rem; display: flex; align-items: baseline; gap: .4rem; flex-wrap: wrap; }
.tag { font-weight: 500; font-size: .72rem; color: #666; }
.greedy { background: #fff7f0; }
.optimal { background: #f0f8ff; }
.count { font-size: 1.8rem; font-weight: 700; line-height: 1; }
.count small { font-size: .8rem; font-weight: 500; color: #666; }
.mono { font: 13px ui-monospace, monospace; color: #333; margin-top: .25rem; word-break: break-word; }
.verdict { font-size: .95rem; font-weight: 600; min-height: 1.2em; margin: .4rem 0 0; }
.verdict.win { color: #0a7d33; }
.verdict.lose { color: #c0392b; }
@media (max-width: 460px) { .cards { grid-template-columns: 1fr; } }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const coinsEl = document.getElementById('coins');
const amountEl = document.getElementById('amount');
const errEl = document.getElementById('err');
const gCount = document.getElementById('gCount');
const gBreak = document.getElementById('gBreak');
const oCount = document.getElementById('oCount');
const oBreak = document.getElementById('oBreak');
const verdict = document.getElementById('verdict');

// Greedy: always take the largest coin that still fits.
function greedy(coins, amount) {
  const used = {};
  let left = amount, total = 0;
  for (const c of [...coins].sort((a, b) => b - a)) {
    while (left >= c) { left -= c; used[c] = (used[c] || 0) + 1; total++; }
  }
  return left === 0 ? { total, used } : null; // null = greedy got stuck
}

// Optimal: dynamic programming over every amount from 0..target.
function optimal(coins, amount) {
  const INF = Infinity;
  const best = Array(amount + 1).fill(INF);
  const pick = Array(amount + 1).fill(-1);
  best[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (c <= a && best[a - c] + 1 < best[a]) { best[a] = best[a - c] + 1; pick[a] = c; }
    }
  }
  if (best[amount] === INF) return null;
  const used = {};
  let a = amount;
  while (a > 0) { used[pick[a]] = (used[pick[a]] || 0) + 1; a -= pick[a]; }
  return { total: best[amount], used };
}

function fmt(used) {
  return Object.keys(used).sort((a, b) => b - a)
    .map(c => `${c}×${used[c]}`).join('  +  ') || '—';
}

function render() {
  errEl.textContent = '';
  verdict.textContent = '';
  verdict.className = 'verdict';
  const coins = coinsEl.value.split(',').map(s => parseInt(s.trim(), 10)).filter(n => n > 0);
  const amount = parseInt(amountEl.value, 10);
  if (!coins.length) { errEl.textContent = 'Enter at least one positive coin value.'; return; }
  if (!(amount >= 0)) { errEl.textContent = 'Enter a non-negative amount.'; return; }

  const g = greedy(coins, amount);
  const o = optimal(coins, amount);

  gCount.innerHTML = g ? i18nFmt('%total% <small>coins</small>', { total: g.total }) : '<small>can’t make it</small>';
  gBreak.textContent = g ? fmt(g.used) : '';
  oCount.innerHTML = o ? i18nFmt('%total% <small>coins</small>', { total: o.total }) : '<small>impossible</small>';
  oBreak.textContent = o ? fmt(o.used) : '';

  if (!o) {
    verdict.textContent = i18nFmt('%amount% cannot be formed with {%coins%}.', { amount: amount, coins: coins.join(', ') });
  } else if (!g) {
    verdict.textContent = i18nFmt('Greedy got stuck, but the optimum uses %total% coins.', { total: o.total });
    verdict.classList.add('lose');
  } else if (g.total === o.total) {
    verdict.textContent = i18nFmt('Greedy is optimal here ( %total% coins). This coin set is "canonical" for %amount%.', { total: o.total, amount: amount });
    verdict.classList.add('win');
  } else {
    verdict.textContent = i18nFmt('Greedy wasted %v% extra coin(s): %total% vs the optimal %total2%.', { v: g.total - o.total, total: g.total, total2: o.total });
    verdict.classList.add('lose');
  }
  console.log(i18nFmt('coins {%coins%} amount %amount% → greedy %v%, optimal %v2%', { coins: coins.join(', '), amount: amount, v: g ? g.total : 'stuck', v2: o ? o.total : 'impossible' }));
}

coinsEl.addEventListener('input', render);
amountEl.addEventListener('input', render);
render();
Result
Console

The Real Complexity

How hard is coin change, really? It depends on what you count.

  • With a fixed, friendly coin system (like real currency), greedy is O(number of coin types) — essentially instant.
  • For an arbitrary coin set, dynamic programming solves it in O(amount × number of coins). That looks cheap, but it's pseudo-polynomial: the cost grows with the value of the amount, not the number of digits used to write it. Double the amount and you double the work.
  • The general decision version ("can this amount be made with at most k coins, for an arbitrary coin set?") is NP-hard. It's a close cousin of the Knapsack problem and Subset Sum, two of the classic hard problems of computer science.

So coin change is a perfect miniature of a recurring theme: a problem can be easy in practice (because we engineered the inputs to be nice) while its general form is genuinely intractable.

Where It Matters

The change-making problem is not just a classroom curiosity:

  • Cash registers and ATMs dispense bills and coins while minimizing the pieces handed out and the cash held in the drawer.
  • Vending and ticket machines must return exact change from a limited, sometimes unusual, set of denominations.
  • Currency design: governments choose denominations partly so the greedy method stays optimal — a real-world reason this math matters.
  • Logistics and resource allocation: "reach a target using the fewest units" appears whenever you pack, ration, or combine fixed-size pieces.
  • Cryptocurrencies: wallets pick which "coins" (unspent outputs) to combine for a payment — a change-making problem with fees attached.

The same handful of ideas — greedy, dynamic programming, and the boundary where things turn NP-hard — power decisions in all of these systems.

Conclusion

Making change is the kind of problem you'd never expect to be hard — until you change the coins. The greedy method is fast and feels obviously correct, yet it's only guaranteed to work for carefully designed coin systems. Step outside them and you need dynamic programming, and in the fully general case the problem becomes NP-hard.

That arc — intuitive method → surprising failure → real difficulty — is exactly what makes coin change a perfect first look at the limits of algorithms. The next time you get change at a shop, remember: a tiny, beautifully engineered piece of mathematics is making it look easy.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/coin-change/Content licensed under CC BY-NC 4.0.