#include <stdio.h>
#include <stdlib.h>
/*
* Function: divide_amount
* -----------------------
* Given an amount and an array of bills/coins,
* prints how many of each denomination are needed.
*
* Uses a greedy algorithm: always take the largest
* possible denomination first. This is optimal for
* canonical currency systems (like most real-world ones).
*/
void divide_amount(int amount, const int bills_coins[], int size) {
printf("Dividing amount: %d\n\n", amount);
for (int i = 0; i < size; i++) {
int denom = bills_coins[i];
/* Number of this denomination needed */
int count = amount / denom;
if (count > 0) {
printf("%4d-unit: %d\n", denom, count);
amount %= denom; /* Reduce remaining amount */
}
}
/* If amount is not zero here, something is wrong */
if (amount > 0) {
printf("\nWarning: leftover amount = %d (should be 0)\n", amount);
}
}
int main(void) {
int bills_coins[9] = {500, 100, 200, 50, 20, 10, 5, 2, 1};
/* Sort denominations descending for greedy correctness */
/* Use qsort from stdlib */
int size = sizeof(bills_coins) / sizeof(bills_coins[0]);
/* Comparison function for qsort */
int cmp_desc(const void *a, const void *b) {
int x = *(const int *)a;
int y = *(const int *)b;
return y - x; /* descending order */
}
qsort(bills_coins, size, sizeof(int), cmp_desc);
int amount = 9749;
divide_amount(amount, bills_coins, size);
return 0;
}
/*
run:
Dividing amount: 9749
500-unit: 19
200-unit: 1
20-unit: 2
5-unit: 1
2-unit: 2
*/
