Money Change by Greedy Algorithm
Greedy Algorithm is an algorithmic paradigm that builds by a solution piece by piece.
As one can understand by its name, you solve the problem but putting in minimum effort with maximum efficiency.
One such example of such problem is Money Exchange Problem.
Problem Introduction: In this problem, you will design and implement an elementary greedy algorithm used by cashiers all over the world millions of times per day.
Get Sarvesh Dubey’s stories in your inbox
Join Medium for free to get updates from this writer.
Problem Description: 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.
Now, to solve the greedy algorithm, we first have to make a safe move. In this particular case our safe move is to collect maximum number of coins worth value 10 (biggest in this case). Then the remaining of the portion for the second biggest and so on.
Quite an easy problem but as you will continue to go on, the problems will get more complicated and trickier.
Basically, what I did is just divided the total amount with max valued currency and then the remainder with the second max values currency and so on.
Note: Use data types that supports larger values.
