Greedy Coin Changer Program in C

The greedy coin change algorithm makes change for a given amount using the fewest coins possible, by always picking the largest denomination that fits. It works optimally when denominations are canonical (e.g., 1, 5, 10, 25 cents), but may not find the global minimum for arbitrary denomination sets.

Algorithm

Sort denominations in descending order (user must enter them this way).
For each denomination from largest to smallest:
- Use as many of this coin as possible: count = amount / denom.
- Subtract: amount %= denom.
Print the count for each denomination.

C Program

#include <stdio.h>

int main(void)
{
    int num_denominations, coin_list[100], use_these[100];
    int i, owed;

    printf("Enter number of denominations: ");
    scanf("%d", &num_denominations);

    printf("Enter the denominations in descending order: ");
    for (i = 0; i < num_denominations; i++)
        scanf("%d", &coin_list[i]);

    printf("Enter the amount owed: ");
    scanf("%d", &owed);

    for (i = 0; i < num_denominations; i++) {
        use_these[i] = owed / coin_list[i];
        owed        %= coin_list[i];
    }

    printf("\nSolution:\n");
    for (i = 0; i < num_denominations; i++)
        printf("  %d x %d\n", coin_list[i], use_these[i]);

    return 0;
}

Sample Output

Enter number of denominations: 4
Enter the denominations in descending order: 25 10 5 1
Enter the amount owed: 67

Solution:
  25 x 2
  10 x 1
  5 x 1
  1 x 2

Result: 2×25 + 1×10 + 1×5 + 2×1 = 67 ✓ (6 coins total — the minimum for US coins.)

Time and Space Complexity

Metric	Value
Time complexity	O(n) — one pass over denominations
Space complexity	O(n) — two arrays of size n
Optimal?	Yes for canonical coin systems; No in general

When Greedy Fails

For denominations {1, 3, 4} and amount 6: greedy picks 4+1+1 = 3 coins, but the optimal is 3+3 = 2 coins. For such cases, use dynamic programming (coin change DP) instead.

More C Programs

Further reading: The C Programming Language by Kernighan & Ritchie — the definitive C reference.

Greedy Change Making Program in C