The minimum coin problem

The minimum coin problem has various versions usually differing in the expected outcome of the exercise. Since the ways we can solve them are very similar, I will look at the basic problem and will mention a modification at the end of the post.

Problem statement

Given an amount of money and the available coins in dollars, find the least number of coins this amount can be paid without getting any change back.

We will consider banknotes as coins for this exercise and will have infinite number of each coin.

Thinking about it

Before we get our hands dirty with the big bucks, let’s step back and try to find a working algorithm from real life.

How would we act if we came across this problem?

Say that we need to pay $82 at the checkout in the supermarket. Since we assume that we have infinite number of each type of coins (how great it would be!), we grab them from our pocket and place them in front of us in ascending order.

We can use the following face values (all are given in dollars): 1, 2, 5, 10, 20, 50 and 100.

Yes, the easiest way would be to pay with the $100 note (only 1 coin) but we would get some change in return, which is not allowed. So we need to move on to the first coin less than or equal to the amount to be paid and this is the $50 coin.

We select one of them, and quickly subtract $50 from $82, which gives a result of $32. This is the remainder we will work with in the next step.

Now we need to start the same process again. We should select the next coin less than or equal to $32. We take a $20 coin here and after subtracting it from $32 we will be left with $12.

Repeating the selection and the subtraction again, we take a $10 coin, subtract it from $12 and the leftover is $2, which can be paid with a single $2 coin.

Let’s sum up what we have just done. We kept subtracting the face value of greatest coin that is less than or equal to the actual amount until we got zero. (This is always possible due to the variety of the face values.)

Building blocks in JavaScript

Now that we discovered one way of solving the problem, let’s find some corresponding JavaScript logic.

We can store the coin face values in an array and can use a while loop for doing the repetitive subtractions. The main logic will be placed inside the while block.

Two things to note here. First, we will need to set up the condition of the while block carefully to avoid getting into an infinite loop. We will iterate over the coins array and getting to the last (or first) element of the array seems to be a reasonable condition. After this element has been reached and used, the iteration will be over.

Secondly (and probably this is a bit harder), we will keep subtracting the values of the coins from the amount. Our initial amount ($82 here) will change as soon as we subtract $50 from it. The new result ($32) needs to be considered as the amount in the next round, therefore we should store it somewhere.

We can declare a variable which stores these new amounts. It is a reasonable idea because we only need to use an amount once. After we subtracted the relevant coin, we will get a new amount to work with and the previous one can be abandoned, i.e. we can override its value with the new one.

As we need to determine the number of coins the amount given is paid with, we will need to set up a counter variable as well.

Solution

Enough of talk, let’s see the code!

We start by declaring the variables for the amount and the coins as well as the function:

const PRICE = 82;
const COINS = [1, 2, 5, 10, 20, 50, 100];

function numberOfCoins(price, coins) {

}

numberOfCoins accepts two parameters, price and coins.

Next, we can declare the variables for the counter, the temporary amount and the condition for the while loop inside the function:

let i = coins.length - 1;
let tempPrice = price;
let counter = 0;

i represents each coin in COINS and will be used as the condition for the while loop and tempPrice will store the current price we are getting by subtracting the relevant coin from the actual amount.

Note that all of them are declared with let as they will be modified inside the loop.

The while statement can look like this:

while (i >= 0) {
  if (tempPrice - coins[i] >= 0) {
    tempPrice -= coins[i];
    counter++;
  } else {
    i--;
  }
}

i’s initial value is the coin with the greatest face value ($100) that is, the last element of COINS.

We have a simple if/else statement inside the while block and it will be checked on each iteration.

How can we decide if a coin can be used to pay the current amount? If we subtract its face value from the amount (tempPrice) and we get a negative value, the coin cannot be used because the value of the coin is greater than the amount to be paid. For example, $82 - $100 is negative, so we can’t pay with the $100 coin. This time the condition is not met and we decrease the value of i (i.e. we move on to the coin with the next greatest face value).

What if the condition is met? We can use the coin then! We decrease tempPrice with the value of the coin, this is how we get the new amount to check next time. We also increase counter by 1 each time we use a coin.

Finally, we return counter to get the number of coins.

The final code can look like this:

function numberOfCoins(price, coins) {
  let i = coins.length - 1;
  let tempPrice = price;
  let counter = 0;

  while (i >= 0) {
    if (tempPrice - coins[i] >= 0) {
      tempPrice -= coins[i];
      counter++;
    } else {
      i--;
    }
  }

  return counter;
}

If the function is called with the given PRICE and COINS, we will get the answer:

numberOfCoins(PRICE, COINS); // 4

These coins are the $50, $20, $10 and $2 coins.

Considerations

Can we list how many of each type of coins need to be used?

Yes, we can, but will need to make a small change in the function.

Let’s call the new function getCoins and store the quantity of each coin in an object:

function getCoins(price, coins) {
  let i = coins.length - 1;
  let tempPrice = price;

  const countingObj = coins.reduce((obj, coin) => {
    obj[coin] = 0;
    return obj;
  }, {});

  while (i >= 0) {
    if (tempPrice - coins[i] >= 0) {
      tempPrice -= coins[i];
      countingObj[coins[i]]++;
    } else {
      i--;
    }
  }

  return countingObj;
}

The object can be created using reduce and each key will represent the face value of a coin. The values of the keys will initially be 0.

As the counter has been replaced with countingObj we need to change the logic as well. Instead of increasing the counter by 1, we will increase the value of the relevant key each time a “good” coin is found.

If we call getCoins with the same PRICE and COINS parameters, we will get an object returned with the correct number of coins:

{ '1': 0, '2': 1, '5': 0, '10': 1, '20': 1, '50': 1, '100': 0 }

Conclusion

The minimum coin is a nice little exercise, which can be solved in only few lines of code. The presented solutions, of course, are not the only correct ones and I encourage the reader to share their solution if they know a different one.

I hope that you have found this post useful. If so, see you next time.