Greedy algorithm for coin change problem

The greedy algorithm can be used to solve the coin change problem to get the optimal solution. So in this article, I will try to explain what is a greedy algorithm? How greedy algorithm can be used to solve the coin change problem.

What is a greedy algorithm?

The greedy algorithm is an approach to solve a problem by finding the best/optimal solution at a given point of instance or to its subproblem. As a result, the overall solution will be an optimal solution. It is usually used for optimization problem-solving.

For example, if you want to reach the “destination place” from the “source place” with a minimum distance to travel, there might be multiple routes with the intermediary substation with a variable length of distance. We will choose the nearest substation with the minimum distance, and then the next substation with the minimum distance till we reach the destination place we will continue the process.

In the above example, it might not give the least distance route always. It is just used to explain the concept of the greedy algorithm and how it works. Now, let’s code one problem with the greedy algorithm and find the optimal solution for that problem. The problem we are going to look at is called the coin change problem.

Coin change problem using the greedy algorithm

We will find the minimum number of coins required for a given sum. The available coins are 1, 5, and 10 denominations. So, we will find how many 10 coins, 5 coins, and 1 coin are required to make the change for the given sum.

Pseudocode for 1, 5, and 10 denomination coin change problem

Let’s define the user input and output for the program code.

Input: the sum for which change is required.

Output: Minimum number of coins with denominations 1, 5, and 10 for change of sum.

Algorithm coinChange(sum){
    //all the coinValues are initialze to 0 at beginning
    coin10, coin5, coin1 = 0
    while True do
        if sum > 9 then
            sum = sum - 10
            coin10 = coin10 + 1
        else if sum > 4 then
            sum = sum - 5
            coin5 = coin5 + 1
        else
            coin1 = sum
            break
  print(coin10,coin5,coin1)
}

Source code for coin change problem in python3

def coinChange(sum):
	coin10, coin5, coin1 = 0, 0, 0
	while True:
		if sum > 9:
			sum = sum - 10
			coin10 = coin10 + 1
		elif sum > 4:
			sum = sum - 5
			coin5 =  coin5 + 1
		else:
			coin1 = sum
			break
	print(f"10 coins:{coin10} \n 5 coins:{coin5}\n 1 coins:{coin1}")
coinChange(eval(input("enter the sum:")))

Run time complexity of the coin change algorithm

The above algorithm runs approximately in O(n) run time. Every time we deduct the denomination from the sum till the sum becomes zero.

The same problem can be solved in constant time with O(1)

Program code for the coin change problem in O(1) run time.

def coinChange(sum):
	coin10 = sum//10
	sum = sum%10
	coin5 = sum//5
	sum = sum%5
	coin1 = sum
	print(f"10 coins:{coin10} \n 5 coins:{coin5}\n 1 coins:{coin1}")
coinChange(eval(input("enter the sum:")))

To be more precise, the above algorithm completes in O(7) run time. If each line of code execution takes the unit time to complete. For any value of the sum, it takes constant time to find it and complete the algorithm.

A greedy algorithm will not give always an optimal solution for the coin change problem

For all the possible denominations of coins, the greedy algorithm will not give the optimal solution. Only for some suitable combination of coin denominations, the greedy algorithm will give the optimal solution. One such example is the above problem with denominations 1, 5, and 10.

However, let’s give the counterexample such that the greedy algorithm for the coin change problem will not give the optimal solution. You have the coins of denominations 1, 3, and 4. In order to make the change for sum 6, the greedy algorithm will give 4+1+1. But the optimal solution for the above coin change will be 3+3 with only 2 coins of 3.

Therefore, the greedy algorithm will not always give the optimal solution for every coin denomination combination.

Conclusion

To summarize, you have known that the greedy algorithm is just an approach to solve the problem which can be optimized. One such problem where the greedy algorithm can be used is the coin change problem as described above with some limitations. Besides the coin change problem some other problems where the greedy algorithm can be used are listed below:

If you like the article then do share and comment on the article. To get the latest updates on the blog post do subscribe to this website by clicking on the subscribe form given on the right side of this page. Keep learning and sharing.