Changing Money
This problem was taken from the Coursera Data Structures and Algorithms Specialization, specifically from the Algorithmic Toolbox Course, Week 3: Greedy Algorithms, that I’ve recently completed. If you are taking that course or plan to take that course, please don’t look ahead at the solution as it will be against the Honor Code and won’t do you any good.
Problem Introduction
In this problem, you will design an algorithm for changing money optimally.
Problem Description
Task: The goal in this problem is to find the minimum number of coins needed to change the input value (an integer) into coins with denominations 1, 5, and 10.
Input Format: The input consists of a single integer m
Constraints: 1 ≤ m ≤ 10^3
Output Format: Output the minimum number of coins with denominations 1, 5, 10 that changes m.
Time Limits: C: 1 sec, C++: 1 sec, Java: 1.5 sec, Python: 5 sec. C#: 1.5 sec, Haskell: 2 sec, JavaScript: 3 sec, Ruby: 3 sec, Scala: 3 sec.
Memory Limit: 512 Mb
Sample 1
Input:
2
Output:
2
Explanation:
2 = 1 + 1.
Sample 2.
Input:
28
Output:
6
Explanation:
28 = 10 + 10 + 5 + 1 + 1 + 1.
What To Do
To design a greedy algorithm for this problem, play with small values of m (consider, for example, sample tests).
My Solution:
Explanation:
Well, it’s a really simple algorithm, really. No need to implement a complex algorithm, this naive algorithm does the job just fine. If you don’t understand this, simply respond to this article and I’ll surely give you a reply and hopefully, a satisfactory explanation.
If you can think of any other way to improve this algorithm or if you could point out something that you think I did wrong, you’re more than welcome to reach out to me by responding to this and pointing out the mistakes. If you like this solution, please hit the “Recommend” button below, it’ll mean a lot to me. Thanks.
