Coin Change Problem using Greedy Algorithm

In this post, we will look at the solution for Coin Change Problem using Greedy Algorithm.

But before that, let’s understand what Greedy Algorithms are in the first place.

1 – What are Greedy Algorithms?

Greedy Algorithms are basically a group of algorithms to solve certain type of problems. The key part about greedy algorithms is that they try to solve the problem by always making a choice that looks best for the moment.

Also, once the choice is made, it is not taken back even if later a better choice was found. Greedy algorithms try to directly arrive at the final solution.

This approach makes greedy algorithms quite optimal. However, the difficult part is to find a strategy that always provides optimal results.

2 – Introducing the Coin Change Problem

The famous coin change problem is a classic example of using greedy algorithms.

Let’s understand what the problem is.

According to the coin change problem, we are given a set of coins of various denominations. Consider the below array as the set of coins where each element is basically a denomination.

{1, 2, 5, 10, 20, 50, 100, 500}

Our task is to use these coins to form a sum of money using the minimum (or optimal) number of coins. Also, we can assume that a particular denomination has an infinite number of coins. In other words, we can use a particular denomination as many times as we want.

As an example, if we have to achieve a sum of 93, we need a minimum of 5 coins as below:

50 20 20 2 1

Going by the greedy approach, we first pull out a coin of denomination 50. We have 43 left to achieve. The next highest coin is 20 and therefore we pull that out. Then, we have 23 left. After that, we pull out another coin of 20 resulting in 3 left. We can then pull out 2 & 1 to finally reach 0 meaning we have reached a sum of 93.

As you can see, at each step, the algorithm makes the best possible choice. In this case, the highest denomination possible.

Below is an illustration that depicts the overall process:

As you can see, at each step we use the highest possible coin from the denominations. At last, we are able to reach the value of 93 just by using 5 coins.

3 – Coin Change Problem Greedy Approach Implementation

Below is an implementation of the above algorithm using C++. However, you can use any programming language of choice.

#include <bits/stdc++.h>

std::vector<int> denominations = {1, 2, 5, 10, 20, 50, 100, 500};

void findMinCoins(int value)
{
    sort(denominations.begin(), denominations.end());

    std::vector<int> answer;

    for (int i = denominations.size() - 1; i >= 0; i--)
    {
        while (value >= denominations[i])
        {
            value = value - denominations[i];
            answer.push_back(denominations[i]);
        }
    }

    std::cout << "The value can be achieved in " << answer.size() << " coins as below:" << std::endl;

    for (int i = 0; i < answer.size(); i++)
    {
        std::cout << answer[i] << " ";
    }
}

int main()
{
    int value = 93;
    findMinCoins(value);
    return 0;
}

We store the denominations in a vector. If you want to know more about vectors or arrays, please check out this post. The values are kept in ascending order and then, we make sure to traverse from the end. This is because the higher denominations will be at the end of the array.

At each iteration, we keep comparing whether the remaining value is greater than the denomination. If yes, we deduct otherwise, we move to the next lower denomination. Finally, we have list of all the denominations we have used to reach the given value.

4 – Issue with Greedy Algorithm Approach

While the coin change problem can be solved using Greedy algorithm, there are scenarios in which it does not produce an optimal result.

For example, consider the below denominations.

{1, 5, 6, 9}

Now, using these denominations, if we have to reach a sum of 11, the greedy algorithm will provide the below answer. See below illustration.

Here, accordingly to the Greedy algorithm, we will end up the denomination 9, 1, 1 i.e. 3 coins to reach the value of 11. However, if you look closely, there is a more optimal solution. And that is by using the denominations 5 & 6. Using them, we can reach 11 with only 2 coins.

However, the way greedy approach works, this solution was never considered. And this can be thought of as a shortcoming of greedy approach. It does not work in the general cases.

In the next post, we will be looking at a better solution to the coin change problem using dynamic programming.

If you have any comments or queries, please share in the comments section below.