If you are learning C programming, you might have encountered some problems that require you to break an amount into the smallest possible number of bank notes. For example, you might want to find out how many $100, $50, $20, $10, $5, $2, and $1 bills you need to pay a certain amount. In this program, I will show you how to write a C program that can break any amount into the smallest possible number of bank notes.
What is the Smallest Possible Number of Bank Notes?
The smallest possible number of bank notes is the minimum number of bills that can add up to a given amount. For example, if the amount is $237, the smallest possible number of bank notes is 2 x $100 + 1 x $20 + 1 x $10 + 1 x $5 + 1 x $2. This is because we cannot use fewer than 2 x $100 bills to pay $237, and we cannot use fewer than 1 x $20 bill to pay the remaining $37, and so on.
To find the smallest possible number of bank notes, we need to use a greedy algorithm. A greedy algorithm is a method that makes the optimal choice at each step without looking ahead. In other words, we always choose the largest possible bank note that can be subtracted from the amount without making it negative. We repeat this process until the amount becomes zero.
C Program
To write a C program that can break an amount into the smallest possible number of bank notes, we need to do three things:
- Declare a function that takes one parameter (the amount) and prints the number of each bank note.
- Define the function using a while loop and a series of if-else statements to subtract the largest possible bank note from the amount and increment the corresponding counter.
- Write a main function that prompts the user to enter the amount and calls the break_amount function with the amount as an argument.
Here is how our program looks like:
#include <stdio.h>
// A function to break an amount into the smallest possible number of bank notes
void break_amount(int amount) {
// Declare some variables to store the number of each bank note
int n100, n50, n20, n10, n5, n2, n1;
// Initialize the variables to zero
n100 = n50 = n20 = n10 = n5 = n2 = n1 = 0;
// Use a while loop to subtract the largest possible bank note from the amount until it becomes zero
while (amount > 0) {
// If the amount is greater than or equal to 100, subtract 100 and increment n100
if (amount >= 100) {
amount -= 100;
n100++;
}
// Else if the amount is greater than or equal to 50, subtract 50 and increment n50
else if (amount >= 50) {
amount -= 50;
n50++;
}
// Else if the amount is greater than or equal to 20, subtract 20 and increment n20
else if (amount >= 20) {
amount -= 20;
n20++;
}
// Else if the amount is greater than or equal to 10, subtract 10 and increment n10
else if (amount >= 10) {
amount -= 10;
n10++;
}
// Else if the amount is greater than or equal to 5, subtract 5 and increment n5
else if (amount >= 5) {
amount -= 5;
n5++;
}
// Else if the amount is greater than or equal to 2, subtract 2 and increment n2
else if (amount >= 2) {
amount -= 2;
n2++;
}
// Else if the amount is equal to 1, subtract 1 and increment n1
else if (amount == 1) {
amount -= 1;
n1++;
}
}
}
Output
The smallest possible number of bank notes are:
2 x $100
1 x $20
1 x $10
1 x $5
1 x $2
Conclusion
In this program, I have shown you how to write a C program that can break any amount into the smallest possible number of bank notes using a greedy algorithm. I hope you have learned something useful and enjoyed reading this post. If you have any questions or feedback, please leave a comment below. Thank you for reading!
We love your feedback and invite you to comment on our articles, exercises, examples, quizzes and others. Your feedback helps us make our content awesome and serve you better. Please leave a comment and tell us what you think. How did our content help you learn something new? Thank you for being a part of our community!