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 , one better than the other, and a : Go and Python. two different algorithms comparison between two languages As always, these problems are provided by the wonderful newsletter DailyCodingProblem, which you can subscribe to . Check it out and try to solve your challenges, too! here 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: cents. Find the minimum number of coins required to make n You can use standard American denominations, that is, 1¢, 5¢, 10¢, and 25¢. , return since we can make it with a 10¢, a 5¢, and a 1¢. For example, given n = 16 3 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: This means that it is really easy, with this system, to build amounts that are multiples of 5. each one of them, except for the 1¢, is a multiple of 5. Given this, we can then use the 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. 1¢ to “adjust” So, Since each number ending with a 0 or a 5 is a multiple of 5, . Here’s a graphic explanation: how many 1¢ coins are we forced to use at most? we are forced to use at most four 1¢ coins before swapping all of them with a 5¢ Besides that, 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 . So, we should always focus on using higher-value coins first, followed by the others in decreasing order. which coins should we use first? we are reaching our target amount faster, we are also using fewer coins to do so Let’s recap a bit: First off, . To do so, we can reverse the process: finding the nearest multiple of 5 by subtracting 1¢ coins from the target value; we need to find the nearest multiple lesser than our target values. At that point, we need to start adding 1¢ coins After that, , starting from the highest 25¢ to the lowest 5¢ coin, we can add coins for each coin value and update our value 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 to store the coins we used during the process. After that, we apply the first point of our previous argument: our is not a multiple of 5 ( ) we This way, we add 1¢ coins until we hit a multiple of 5. coins targetValue targetValue % 5 != 0 increase the coin counter by one and decrease targetValue by one: After that, we apply the second point: . So while 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 to update it. Once is lesser than 25, we can’t use a 25¢ coin to get to it, so we stop. we add the other coins, starting from the 25¢ one, until they can’t fit in the targetValue anymore targetValue targetValue targetValue This same process is also run for the 10¢ coins: once the is less than 10, we must stop using 10¢ coins. targetValue At this point, our 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, 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 , which will be 1 if is 5 and 0 if is 0. targetValue targetValue targetValue/5 targetValue targetValue 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 . Suppose we have a 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 : This is basically dividing! if we look closer at the process, it really is simple division targetValue targetValue After the division, For this reason, we can substitute the for loops in the algorithm with a simple division! Here’s the new algorithm: we get rid of the remainder and keep the integer part, and that’s it. https://gist.github.com/NicolaM94/77c30143d002d21342bcf33bcac30246?embedable=true#file-minimumcoinstwo-go The algorithm is pretty much the same; the . Here, we substitute them with the simple division of by the coin we are considering. We first add as many coins as and then we subtract the coin value from 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. only difference resides in the missing for loops targetValue targetValue/{coinValue} targetValue A Python version Maybe you noticed that there is something with the division. For example, for a , : how come we can simply add the result to our coins, obtaining 3 instead? For this reason, a division between two un-typed integers gives back an integer, the integer part of 3,6. Unlike Go, For this reason, the same algorithm in Python would need some more type conversions here and there. Here’s the result: wrong targetValue = 90 targetValue/25 = 3.6 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. Python has a more practical approach: the result of any division is always a floating point number. 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 for conversion. For example then: // int print(90/25)   #3.6
print(90//25)  #3 Time complexity Let’s start with . It’s pretty clear that it , with a time complexity O(n): the number of operations depends entirely on the size of the input . . The other two for loops run in linear time instead, depending on the size of . the first algorithm runs in linear time targetValue The first for loop only runs from 1 to 4 times, so we can consider it constant time targetValue , and also its Python variant, of course, : 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 , requiring at most 10 steps to give out a solution. The second algorithm, though is way better runs in constant time O(1) 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 page, so if you can, and you are willing to share a Kofi, feel free to do so! Ko-fi As always, a big thanks for reading Nicola Also published . here

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.

Daily Coding Problem: Minimum Coins Count

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Daily Coding Problem: Building an Algorithm to Calculate Huge Factorials!

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

Daily Coding Problem: Building an Algorithm to Calculate Huge Factorials!

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps