Understanding the Coin Change Problem in a Greedy Approach
.
Introduction
In the world of algorithms, one of the essential concepts is the Coin Change algorithm. This algorithm is particularly important when dealing with money and currencies.
For instance, if you’re in market and you don’t have Google pay or Paytm and you want to make change for a given amount of rupees using the least possible number of coins, the Coin Change algorithm can help you achieve that efficiently.
In this article, we’ll explore the Coin Change algorithm in a beginner-friendly manner, using simple English to make it accessible to all.
.
Definition
The Coin Change algorithm, in a greedy approach, aims to find the minimum number of coins needed to make change for a given amount.
In our case, we’ll use Indian currency, where the available coin denominations are 1, 2, 5, 10 and 20 rupees.
.
Working of the Coin Change Algorithm
- Start with the highest denomination coin (20 rupees).
.
- Check how many of these coins can fit into the given amount without exceeding it.
- Subtract the total value of these coins from the given amount.
- Move to the next lower denomination coin (10 rupees) and repeat steps 2 and 3.
- Continue this process until you reach the lowest denomination coin (1 rupee).
.
Algorithm of Coin Change
Here is a simple step-by-step algorithm for the Coin Change problem in the context of Indian currency
- Initialize the total count of coins as 0.
- Start with the highest denomination coin.
- While the given amount is greater than 0:
- Find the maximum number of the current denomination coin that can be used without exceeding the amount.
- Add this count to the total count of coins.
- Subtract the total value of these coins from the given amount.
- Move to the next lower denomination coin.
- Repeat steps 3 and 4 until you’ve considered all available denominations.
.
Example of Coin Change
Let’s say you want to make change for 87 rupees using Indian currency. Here’s how the Coin Change algorithm works in this scenario:
1. Start with a 20-rupee coin: You can use 4 of them (4 * 20 = 80 rupees).
.
2. Move to a 10-rupee coin: You can’t use it because the total would be higher than 87.
3. Move to a 5-rupee coin: You can use 1 of them (1 * 5 = 5 rupees).
.
4. Finally, use 2 one-rupee coins.
.
You’ll need a total of 4 + 1 + 1 = 6 coins to make change for 87 rupees.
.
Greedy approach doesn’t always guarantee the optimal solution
.
Note – Greedy approach doesn’t always guarantee the optimal solution for all coin systems and can lead to suboptimal results in certain scenarios.
Consider a coin system with denominations: 1, 3, 4.
Now, let’s say you want to make change for 6 units using the greedy approach. Here’s how the greedy algorithm would work
.
1. Start with the highest denomination coin (4 units).
2. Subtract 4 from 6, resulting in 2 units.
3. Now, select the highest denomination coin again, which is 1 unit.
4. Use two 1-unit coins to make up the remaining 2 units.
5. Using the greedy approach, you would end up using four coins (4, 1, 1) to make change for 6 units.
6. But the answer is (3, 3) that is minimum coin change.
.
But the Indian government and all other governments of different countries knew this. Therefore, they made such denominations that solves all these points.
1. The Renard Series is used by countries where the ratios between neighboring denominations of money is 1:2 or 1:2.5. The denomination should be twice or twice and a half times the preceding denomination, allowing for value exchange in a maximum of three denominations.
2. It was proposed by a French Army Engineer Colonel Charles Renard in 1870.
3. The smallest odd – 1 is mandatory by which we can sum up to any number.
4. The smallest even – 2 is mandatory.
.
Source Code for Coin Change Problem
// COMPUTER GEEK – compgeek.co.in
// Write a program for Coin Change Problem
#include <stdio.h>
int main()
{
// Array of available coin denominations in Indian currency
int denominations[] = {20, 10, 5, 2, 1};
// Initialize the total count of coins as 0
int totalCoins = 0;
// Input: Get the amount from the user
int amount;
printf(“Enter the amount in rupees: “);
scanf(“%d”, &amount);
// Iterate through the denominations
for (int i = 0; i < 5; i++)
{
// Find the maximum number of the current denomination coin
int numCoins = amount / denominations[i];
// Update the total count of coins
totalCoins += numCoins;
// Subtract the total value of these coins from the given amount
amount -= numCoins * denominations[i];
// Output: Display the number of coins used for the current denomination
printf(“%d-rupee coins: %d\n”, denominations[i], numCoins);
}
// Output: Display the total number of coins used
printf(“Total number of coins: %d\n”, totalCoins);
return 0;
}
// COMPUTER GEEK – compgeek.co.in
// Write a program for Coin Change Problem
#include <iostream>
int main()
{
// Array of available coin denominations in Indian currency
int denominations[] = {20, 10, 5, 2, 1};
// Initialize the total count of coins as 0
int totalCoins = 0;
// Input: Get the amount from the user
int amount;
std::cout << “Enter the amount in rupees: “;
std::cin >> amount;
// Iterate through the denominations
for (int i = 0; i < 5; i++)
{
// Find the maximum number of the current denomination coin
int numCoins = amount / denominations[i];
// Update the total count of coins
totalCoins += numCoins;
// Subtract the total value of these coins from the given amount
amount -= numCoins * denominations[i];
// Output: Display the number of coins used for the current denomination
std::cout << denominations[i] << “-rupee coins: ” << numCoins << std::endl;
}
// Output: Display the total number of coins used
std::cout << “Total number of coins: ” << totalCoins << std::endl;
return 0;
}
// COMPUTER GEEK – compgeek.co.in
// Write a program for Coin Change Problem
import java.util.Scanner;
public class CoinChangeAlgorithm
{
public static void main(String[] args)
{
// Array of available coin denominations in Indian currency
int[] denominations = {20, 10, 5, 2, 1};
// Initialize the total count of coins as 0
int totalCoins = 0;
// Input: Get the amount from the user
Scanner scanner = new Scanner(System.in);
System.out.print(“Enter the amount in rupees: “);
int amount = scanner.nextInt();
// Iterate through the denominations
for (int i = 0; i < 5; i++)
{
// Find the maximum number of the current denomination coin
int numCoins = amount / denominations[i];
// Update the total count of coins
totalCoins += numCoins;
// Subtract the total value of these coins from the given amount
amount -= numCoins * denominations[i];
// Output: Display the number of coins used for the current denomination
System.out.println(denominations[i] + “-rupee coins: ” + numCoins);
}
// Output: Display the total number of coins used
System.out.println(“Total number of coins: ” + totalCoins);
}
}
# COMPUTER GEEK – compgeek.co.in
# Write a program for Coin Change Problem
# Array of available coin denominations in Indian currency
denominations = [20, 10, 5, 2, 1]
# Initialize the total count of coins as 0
total_coins = 0
# Input: Get the amount from the user
amount = int(input(“Enter the amount in rupees: “))
# Iterate through the denominations
for denomination in denominations:
# Find the maximum number of the current denomination coin
num_coins = amount // denomination
# Update the total count of coins
total_coins += num_coins
# Subtract the total value of these coins from the given amount
amount -= num_coins * denomination
# Output: Display the number of coins used for the current denomination
print(f”{denomination}-rupee coins: {num_coins}”)
# Output: Display the total number of coins used
print(“Total number of coins:”, total_coins)
Time Complexity of Coin Change Problem
If you see the code, only one for loop is there, So the greedy Coin Change algorithm has a time complexity of O(n), where n is the number of available coin denominations.
.
Space Complexity of Coin Change Problem
The space complexity is O(1) since it only requires a constant amount of additional memory.
.
Advantages of Coin Change Problem
1 Simple and easy to understand.
2 Efficient for standard coin systems like Indian currency.
3 The algorithm has a time complexity of O(n), this means it can calculate the change efficiently, even for larger amounts, making it suitable for real-time applications like vending machines.
4 The space complexity is O(1), meaning it requires only a constant amount of memory, regardless of the input size.
.
Disadvantages of Coin Change Problem
1 Greedy approach may not work for all coin systems. It might not find the optimal solution in some cases.
2 In terms of a real-world scenario, if you are a trader or an individual and you are unable to make change because you lack the required coins denomination, you must spend more than the maximum number of coins.
.
Applications of Coin Change Problem
1 Used in vending machines to give change efficiently.
2 Useful in finance and banking systems for currency conversion.
Test Yourself
Q1- Explain the working of the Coin Change algorithm in a greedy approach.
The Coin Change algorithm in a greedy approach involves starting with the highest coin denomination and iteratively selecting the maximum number of coins of that denomination that can be used without exceeding the given amount. This process continues with lower denominations until the amount is completely covered or no more denominations can be used.
Q2- In what real-world scenarios is the Coin Change algorithm not suitable?
The greedy approach may not be suitable when the coin system lacks a well-defined pattern, or when specific denominations are missing, leading to suboptimal solutions.
Q3- How can coin denominations be designed to ensure the greedy approach works optimally?
Coin denominations should be carefully designed so that one denomination is a multiple of the lower consecutive denominations. This ensures the greedy approach works optimally.
Q4- What is the space complexity of the Coin Change algorithm?
The space complexity is O(1) because it requires a constant amount of memory, regardless of the input size.
Q5- What is the time complexity of the greedy Coin Change algorithm?
1. O(1)
2. O(n)
3. O(log n)
4. O(n^2)
Ans – (2)
Explanation – The greedy Coin Change algorithm has a time complexity of O(n), where n is the number of available coin denominations
Q6- What is the primary objective of the Coin Change algorithm in a greedy approach?
1. To find the maximum number of coins needed
2. To minimize the number of coins needed
3. To maximize the value of coins used
4. To find the minimum amount of change possible
Ans – (2)
Explanation – To minimize the number of coins needed
Q7- How can coin denominations be designed to ensure the greedy approach works optimally?
1. By making each denomination completely independent of the others
2. By ensuring each denomination is a multiple of the lower consecutive denominations
3. By using prime numbers as denominations.
4. By randomly selecting denominations
Ans – (2)
Explanation – By ensuring each denomination is a multiple of the lower consecutive denominations
Q8- You are given infinite coins of denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. This problem can be solved using ____________
1. Greedy algorithm
2. Dynamic programming
3. Divide and conquer
4. Backtracking
Ans – (2)
Explanation – The coin change problem has overlapping subproblems (the same subproblems are solved numerous times) and optimum subproblems (the solution to the problem can be obtained by finding optimal solutions to the subproblems). Thus, dynamic programming can be utilized to address the coin change problem.
Q9- Suppose you have coins of denominations 1, 3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm produce an optimal answer?
1. 14
2. 10
3. 6
4. 100
Ans – (4)
Explanation – The greedy algorithm will choose three coins, {4, 1, 1}, to add up to 6. Nevertheless, two coins {3, 3} is the best response.
In the same way, four coins, {4, 4, 1, 1}, will be chosen in order to add up to 10. However, three coins {4, 3, 3} is the best response.
In addition, five coins {4, 4, 4, 1, 1} will be chosen to add up to 14. That being said, four coins {4, 4, 3, 3} is the best response.
Twenty-five coins {all 4’s} will be chosen for a total of 100, and this number is the optimized response.
Q10- You are given infinite coins of denominations 5, 7, 9. Which of the following sum CANNOT be achieved using these coins?
1. 50
2. 12
3. 13
4. 16
Ans – (3)
Explanation – One way to achieve a sum of 50 is to use ten coins of 5.
A sum of 12 can be achieved by using two coins of 7 and 5.
One way to achieve a sum of 16 is to use one coins of 7 and one coin of 9.
A sum of 13 cannot be achieved.
