Daily Coding Problem: Minimum Coins Count

Welcome everyone with another problem to solve! Today, we are dealing with coins and the minimum number of coins to obtain a certain amount. We are going to use American coins: specifically, 1, 5, 10, and 25 cents coins. This problem will also be the occasion to see two different algorithms, one better than the other, and a comparison between two languages: Go and Python.

As always, these problems are provided by the wonderful newsletter DailyCodingProblem, which you can subscribe to here. Check it out and try to solve your challenges, too!

Ready then? Let’s jump to the problem!

The problem

This problem was asked by Google in an interview, but it’s also a classic problem in math and statistics, expressed in many many versions:

Find the minimum number of coins required to make n cents.

You can use standard American denominations, that is, 1¢, 5¢, 10¢, and 25¢.

For example, given n = 16, return 3 since we can make it with a 10¢, a 5¢, and a 1¢.

The problem does not need further explanations: using 1¢, 5¢, 10¢ and 25¢ coins, we need to find the minimum number of coins to reach a target value n.

Let’s put down some initial considerations first and then see how to write the code to solve this. This will be a long article, but stick with me: I promise it will be interesting!

The logic behind the algorithm

First off, let’s look at the coins: each one of them, except for the 1¢, is a multiple of 5. This means that it is really easy, with this system, to build amounts that are multiples of 5.

Given this, we can then use the 1¢ to “adjust” the value to the amount that we need: in the example above, we can get a value of 16¢ by using one 10¢ coin, one 5¢ coin, and one 1¢ coin. We can add 1¢ coins until we reach another multiple of 5, at which point it is not convenient anymore, and we should use 5¢, 10¢ or 25¢. For example, to build 30¢, we can use one 25¢ and five 1¢, but at that point we should swap for a 5¢ to use less coins.

So, how many 1¢ coins are we forced to use at most? Since each number ending with a 0 or a 5 is a multiple of 5, we are forced to use at most four 1¢ coins before swapping all of them with a 5¢. Here’s a graphic explanation:

Besides that,which coins should we use first? It’s pretty obvious, of course, but using a 25¢ coin is much more worthwhile (…literally, in this case) than using a 10¢ or a 5¢ coin. This is because since we are reaching our target amount faster, we are also using fewer coins to do so. So, we should always focus on using higher-value coins first, followed by the others in decreasing order.

Let’s recap a bit:

• First off, we need to find the nearest multiple lesser than our target values. At that point, we need to start adding 1¢ coins. To do so, we can reverse the process: finding the nearest multiple of 5 by subtracting 1¢ coins from the target value;

• After that, we can add coins for each coin value and update our value, starting from the highest 25¢ to the lowest 5¢ coin, until our coin value exceeds the remaining target value.

Let’s try to build some code.

The code (version one)

Here’s a first version of the code, written in Go language:

https://gist.github.com/NicolaM94/46f9098540343593a8cb6b5c86778641?embedable=true

Let’s break it down: we first init a variable coins to store the coins we used during the process. After that, we apply the first point of our previous argument: our targetValue is not a multiple of 5 ( targetValue % 5 != 0 ) we increase the coin counter by one and decrease targetValue by one: This way, we add 1¢ coins until we hit a multiple of 5.

After that, we apply the second point: we add the other coins, starting from the 25¢ one, until they can’t fit in the targetValue anymore. So while targetValue is lesser or equal to 25, we can use 25¢s to reach it. Again, we add one coin at each loop and subtract 25 from the targetValue to update it. Once targetValue is lesser than 25, we can’t use a 25¢ coin to get to it, so we stop.

This same process is also run for the 10¢ coins: once the targetValue is less than 10, we must stop using 10¢ coins.

At this point, our targetValue holds a value that is less than 10. Since the first step, though, we are carrying on a value that must be a multiple of 5. And since we only divided by 25 and 10, targetValue must still be a multiple of 5. Multiples of 5 below 10 are only 0 and 5, meaning that we only need one more coin or we need none. For this reason, we can simply add to our coin counter targetValue/5 , which will be 1 if targetValue is 5 and 0 if targetValue is 0.

Then, we simply return the coins counter.

The code (version two)

We can do better, though. In the last paragraph, we talked about “dividing by 25 and 10”, because if we look closer at the process, it really is simple division. Suppose we have a targetValue of 90. It’s already a multiple of 5, so we skip the first point and start adding 25¢ coins. At each step of the loop, we add one coin and subtract 25 from targetValue : This is basically dividing!

After the division, we get rid of the remainder and keep the integer part, and that’s it. For this reason, we can substitute the for loops in the algorithm with a simple division! Here’s the new algorithm:

https://gist.github.com/NicolaM94/77c30143d002d21342bcf33bcac30246?embedable=true#file-minimumcoinstwo-go

The algorithm is pretty much the same; the only difference resides in the missing for loops. Here, we substitute them with the simple division of targetValue by the coin we are considering. We first add as many coins as targetValue/{coinValue} and then we subtract the coin value from targetValue as many times as the coins we just added. This simplifies the process a lot, as we’ll see later when talking about time complexity.

A Python version

Maybe you noticed that there is something wrong with the division. For example, for a targetValue = 90 , targetValue/25 = 3.6 : how come we can simply add the result to our coins, obtaining 3 instead? This is because the Go language, as many others, treats the two un-typed numbers as integers and gives back ‘the result of the same type. For this reason, a division between two un-typed integers gives back an integer, the integer part of 3,6. Unlike Go, Python has a more practical approach: the result of any division is always a floating point number. For this reason, the same algorithm in Python would need some more type conversions here and there. Here’s the result:

https://gist.github.com/NicolaM94/45cd6b82d45a473a3b7e24355486100c?embedable=true#file-minimumcoinstwo-py

PS: While doing some research about Python’s division return type, I also discovered you could use the double divide sign // , which I did not know existed, instead of using int for conversion. For example then:

print(90/25)   #3.6
print(90//25)  #3

Time complexity

Let’s start with the first algorithm. It’s pretty clear that it runs in linear time, with a time complexity O(n): the number of operations depends entirely on the size of the input targetValue . The first for loop only runs from 1 to 4 times, so we can consider it constant time. The other two for loops run in linear time instead, depending on the size of targetValue .

The second algorithm, though, and also its Python variant, of course, is way better: since we were able to remove all the for loops, its execution time does not depend on the input size anymore. This means the algorithm now runs in constant time O(1), requiring at most 10 steps to give out a solution.

Conclusion

That’s it for today’s problem: I hope you find it interesting and if you read it to the end, well: thank you so much!

If you found the article useful, please leave a clap or two and share it with someone who could find it useful, too: that would really make my day! I also opened a Ko-fi page, so if you can, and you are willing to share a Kofi, feel free to do so!

As always, a big thanks for reading

Nicola

Also published here.