The coin change problem in JavaScript

Problem

The machine's change

The parking machine returns change. It has one tube for each of the eight euro coins: 1, 2, 5, 10, 20 and 50 cents, 1 € and 2 €. The fewer coins it returns, the less often someone has to refill the tubes. So the change has to use the fewest coins.

The developer does not want to guess and writes a recursion that tries everything: for every coin that fits into the change, "this coin plus the best for the rest", and takes the smallest. The amounts are in cents, and the counter counts the coins tried:

let tries = 0;

function fewest(coins, amount) {
  if (amount === 0) {
    return 0;
  }
  let best = amount + 1;
  for (const coin of coins) {
    if (coin > amount) {
      break;
    }
    tries++;
    const count = fewest(coins, amount - coin) + 1;
    best = Math.min(best, count);
  }
  return best;
}

const coins = [1, 2, 5, 10, 20, 50, 100, 200];
for (const amount of [10, 20, 30]) {
  tries = 0;
  const count = fewest(coins, amount);
  console.log(`${amount} cents: ${count} coins, ${tries} tries`);
}

10 cents: 1 coins, 309 tries
20 cents: 1 coins, 66281 tries
30 cents: 2 coins, 14158888 tries

The answers are right. But for 30 cents the recursion tries 14,158,888 coins, and for 40 cents 3,024,560,419. Change of 63 cents takes 689,951,222,249,236 tries: at a billion a second that is eight days, while the driver waits at the barrier.

The idea

The table

The recursion asks the same thing again and again: the best for 13 cents, for 8 cents, for 3 cents. These are the overlapping subproblems from the previous lesson. Only here up to eight branches leave every amount, one for each coin, and the tree grows even faster.

So we build a table bottom up. A dynamic programming table is described by four things:

What the cell means. best[a] is the fewest coins for exactly a cents.
Where it comes from. The last coin is one of those that fit. So best[a] is 1 + best[a − coin] for the best coin.
In which order it is filled. a − coin is less than a. From left to right everything the cell reads is already done.
Where the answer is. In the last cell, best[change]. The start is best[0] = 0: zero cents need no coins.

This is a DP table: a cell for every subproblem, filled in an order where each cell finds ready the ones it depends on. As in the previous lesson, only the choice in the cell is between more options.

See it

Cell by cell

The table for 9 cents. Watch the arrows: each comes from cell a − coin, and cell a keeps the smallest it has seen:

function change(coins, amount) {
  const best = new Array(amount + 1).fill(0);
  const last = new Array(amount + 1).fill(0);
  for (let a = 1; a <= amount; a++) {
    best[a] = amount + 1;
    for (const coin of coins) {
      if (coin > a) {
        break;
      }
      const count = best[a - coin] + 1;
      if (count < best[a]) {
        best[a] = count;
        last[a] = coin;
      }
    }
  }
  const used = [];
  for (let a = amount; a > 0; a -= last[a]) {
    used.push(last[a]);
  }
  return used;
}

Step by step, in words

change(coins, 9): best[a] is the fewest coins for a cents, last[a] the coin that gets there. best[0] = 0: zero cents need no coins.
For each a from left to right, try every coin up to a: one coin plus the best for what is left, best[a − coin] + 1. The arrow comes from that cell.
a = 5: the coin 1 gives best[4] + 1 = 3, the coin 2 gives best[3] + 1 = 3, the coin 5 gives best[0] + 1 = 1. The cell keeps the smallest, and last remembers the coin.
The coins are ordered small to large, and 10 is already more than 9: the loop stops there. Every cell reads only cells to its left, which are already final.
Back along last: 9 → 7 → 5 → 0. The coins are 2 + 2 + 5. 22 tries for 9 cents, each cell solved once.

const coins = [1, 2, 5, 10, 20, 50, 100, 200];
console.log(change(coins, 9));

[ 2, 2, 5 ]

amount + 1 means "nothing yet": you can never need more coins than cents, because even one-cent coins make exactly amount. So the first coin tried is always better.

The idea

Which coins

The count is not enough: the machine also has to know which coins to drop. So next to best[a] the table also keeps last[a], the coin that leads to the best for a. At the end you start from the change: drop last[a], subtract it, and repeat until you reach 0.

let tries = 0;

function change(coins, amount) {
  const best = new Array(amount + 1).fill(0);
  const last = new Array(amount + 1).fill(0);
  for (let a = 1; a <= amount; a++) {
    best[a] = amount + 1;
    for (const coin of coins) {
      if (coin > a) {
        break;
      }
      tries++;
      const count = best[a - coin] + 1;
      if (count < best[a]) {
        best[a] = count;
        last[a] = coin;
      }
    }
  }
  const used = [];
  for (let a = amount; a > 0; a -= last[a]) {
    used.push(last[a]);
  }
  return used;
}

const coins = [1, 2, 5, 10, 20, 50, 100, 200];
for (const amount of [63, 480]) {
  tries = 0;
  const used = change(coins, amount);
  console.log(`${amount} cents: ${used.join(" + ")}, ${tries} tries`);
}

63 cents: 1 + 2 + 10 + 50, 296 tries
480 cents: 10 + 20 + 50 + 200 + 200, 3460 tries

296 tries for 63 cents instead of 689,951,222,249,236. The table has one cell per cent, and each cell tries at most the eight coins. The work is O(n · k): n cents times k kinds of coin. With k = 8 that is linear in the change.

Try it

Fill in

One coin plus the best for the rest. Which cell does the try read?

function change(coins, amount) {
  const best = new Array(amount + 1).fill(0);
  const last = new Array(amount + 1).fill(0);
  for (let a = 1; a <= amount; a++) {
    best[a] = amount + 1;
    for (const coin of coins) {
      if (coin > a) {
        break;
      }
      const count = best[] + 1;
      if (count < best[a]) {
        best[a] = count;
        last[a] = coin;
      }
    }
  }
  const used = [];
  for (let a = amount; a > 0; a -= last[a]) {
    used.push(last[a]);
  }
  return used;
}

The idea

Why not the biggest coin first?

A cashier does something else: gives the biggest coin that fits, and repeats. For 63 cents that is 50, 10, 2, 1: four coins again. With euro coins this rule always gives the fewest coins. The coins are chosen that way.

But the rule depends on the coin system. With other coins, or when a tube in the machine runs out, "biggest first" can give more coins than needed. When it works and when it fails is the lesson "When greedy fails". The table does not rely on that: it tries every coin for every amount and finds the fewest for any coins.

The idea

In how many ways

Another problem with the same table. The cash machine pays out amounts in notes of 5, 10, 20 and 50 €. The testers want to check every possible bundle for 100 € and ask: how many are there?

Now the cell is count[a]: in how many ways exactly a euros can be made. count[0] = 1, the empty bundle. The outer loop goes over the notes, the inner one over the amounts:

function ways(notes, amount) {
  const count = new Array(amount + 1).fill(0);
  count[0] = 1;
  for (const note of notes) {
    for (let a = note; a <= amount; a++) {
      count[a] += count[a - note];
    }
  }
  return count[amount];
}

const notes = [5, 10, 20, 50];
console.log(ways(notes, 100), "ways");

49 ways

The order of the loops matters. When the fives come entirely before the tens, every bundle is built in one order: first the fives, then the tens. So 5 + 10 and 10 + 5 are the same bundle and are counted once. And here nobody looks for a minimum: the cell adds up the number of ways from the cells to its left.

Try it

Predict the output

How many bundles are there for 20 € with notes of 5, 10 and 20?

function ways(notes, amount) {
  const count = new Array(amount + 1).fill(0);
  count[0] = 1;
  for (const note of notes) {
    for (let a = note; a <= amount; a++) {
      count[a] += count[a - note];
    }
  }
  return count[amount];
}

const notes = [5, 10, 20];
console.log(ways(notes, 20), "ways");

Answer

6 ways

4 ways

3 ways

Try it

Find the bug

A colleague wrote the same counting, but for 100 € it comes out much bigger:

const notes = [5, 10, 20, 50];
console.log(ways(notes, 100), "ways");

48007 ways

Which line has the bug?

Pick the line with the bug.

See it

Measure it: recursion against the table

We count the coins tried: in every recursive call and in every cell. The recursion is not run above 30 cents: at 40 cents it is over 3 billion tries.

Recursion without memory O(2ⁿ)
Table O(n)

Algorithm	n = 10	n = 20	n = 30
Recursion without memory	309	66,281	14,158,888
Table	26	67	117

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

function change(coins, amount) {
  const best = new Array(amount + 1).fill(0);
  const last = new Array(amount + 1).fill(0);
  for (let a = 1; a <= amount; a++) {
    best[a] = amount + 1;
    for (const coin of coins) {
      if (coin > a) {
        break;
      }
      const count = best[a - coin] + 1;
      if (count < best[a]) {
        best[a] = count;
        last[a] = coin;
      }
    }
  }
  const used = [];
  for (let a = amount; a > 0; a -= last[a]) {
    used.push(last[a]);
  }
  return used;
}

Every 10 cents multiply the recursion by about 200, while the table grows by 40–50 tries. The recursion curve is labelled O(2ⁿ): it is exponential, with a base of about 1.7.

More precisely, if you are curious

The same numbers in your language:

let tries = 0;

function fewest(coins, amount) {
  if (amount === 0) {
    return 0;
  }
  let best = amount + 1;
  for (const coin of coins) {
    if (coin > amount) {
      break;
    }
    tries++;
    const count = fewest(coins, amount - coin) + 1;
    best = Math.min(best, count);
  }
  return best;
}

function change(coins, amount) {
  const best = new Array(amount + 1).fill(0);
  const last = new Array(amount + 1).fill(0);
  for (let a = 1; a <= amount; a++) {
    best[a] = amount + 1;
    for (const coin of coins) {
      if (coin > a) {
        break;
      }
      tries++;
      const count = best[a - coin] + 1;
      if (count < best[a]) {
        best[a] = count;
        last[a] = coin;
      }
    }
  }
  const used = [];
  for (let a = amount; a > 0; a -= last[a]) {
    used.push(last[a]);
  }
  return used;
}

const coins = [1, 2, 5, 10, 20, 50, 100, 200];
for (const amount of [10, 20, 30]) {
  tries = 0;
  fewest(coins, amount);
  const plain = tries;
  tries = 0;
  change(coins, amount);
  console.log(`${amount} cents: no memory ${plain}, table ${tries}`);
}

10 cents: no memory 309, table 26
20 cents: no memory 66281, table 67
30 cents: no memory 14158888, table 117

Exercise

The change from the input

Solve it in your editor.

Change. Read the change in cents and print how many coins the machine returns and which. Use change from the lesson.

5 coins: 10 + 20 + 50 + 200 + 200

More tasks

An empty tube. The 1 and 2 cent tubes are empty. Which amounts under 1 € can the machine not return at all? How do you tell from the table? (Hint: the cell stays amount + 1.)
Biggest first. Print the coins from the biggest to the smallest.
How many ways with coins. In how many ways can you pay 1 € with the coins from 1 to 50 cents? And if the 1 € coin is allowed too?

More precisely

Impossible change and very big numbers

Two things the lesson skipped.

More precisely, if you are curious

When the change cannot be returned. If the 1 and 2 cent tubes are empty, 3 cents cannot be returned with anything. Then the cell stays amount + 1, because no try is better. And if last[a] is 0, walking back would spin forever on the spot. So before walking back you check whether best[amount] > amount, and the machine says "No change, please pay the exact amount".

The number of ways grows very fast. In how many ways can you pay 100 € with coins only (10,000 cents, the eight euro coins)?

function ways(notes, amount) {
  const count = new Array(amount + 1).fill(0);
  count[0] = 1;
  for (const note of notes) {
    for (let a = note; a <= amount; a++) {
      count[a] += count[a - note];
    }
  }
  return count[amount];
}

const coins = [1, 2, 5, 10, 20, 50, 100, 200];
console.log(ways(coins, 10000));

1133873304647601

In JavaScript a number is a floating-point value and keeps integers exact up to 2⁵³, about 9 · 10¹⁵. This number is under that limit and exact. For bigger amounts the cells have to be BigInt (0n, 1n), otherwise the answer is quietly rounded.

The table in two dimensions. Counting the ways is really a table "the first i notes × the amount": cell (i, a) is in how many ways a can be made with only the first i notes. Row i is built from the row above it (without note i) and from the cell to the left in the same row (with one more note i). The program keeps only one row and overwrites it from left to right. That is why the outer loop goes over the notes: it walks the rows. The same idea, one row instead of the whole table, comes back in the knapsack problem.

Test

Check yourself

1. What does the cell best[a] in the change table mean?How many coins of value a the machine holdsThe biggest coin that fits into aThe fewest coins that pay exactly a cents

2. Why is the table filled from left to right, from a = 1 up?Cell a only reads cells a − coin, which are to its left and already finalThe order does not matter, right to left works tooBecause the coins are ordered from left to right

3. How does the table say which coins, and not only how many?It counts how many times each cell was usedlast[a] remembers the coin that leads to the best for a; walking back from the change along last gives the coins one by oneIt cannot: you need a second table for every coin

4. In the counting of ways the loops are swapped: the outer one goes over the amounts, the inner one over the notes. What happens?It counts sequences: 5 + 10 and 10 + 5 become two ways, so the number is much biggerIt counts fewer waysNothing, the answer is the same

5. With euro coins, "the biggest coin that fits, and again" gives the fewest coins. So why a table?The greedy rule does not work for euro coinsThe table gives the fewest coins for any coins, while the greedy rule has coin systems where it is wrongThe table is faster than the greedy rule

The coin change problem

Cookies