Course contentsShow
← Computer Science
Lesson 892 of 2,87221. Greedy AlgorithmsFree lesson

Minimum Number of Coins Problem

Make change using fewest coins by always selecting the largest denomination that doesn't exceed remainder.

Minimum Number of Coins Problem

What you'll learn: You'll discover how to make change using the fewest coins possible by always picking the largest coin that fits.


The Core Idea

Imagine you're a cashier giving someone change for $0.87. You don't hand them 87 pennies—you'd give them 3 quarters (75¢), 1 dime (85¢), and 2 pennies (87¢). That's just 6 coins instead of 87!

The Minimum Number of Coins Problem asks: Given an amount and a set of coin denominations, what's the smallest number of coins needed to make that amount?

The Greedy Strategy

The greedy approach is beautifully simple:

  1. Always pick the largest coin that doesn't exceed your remaining amount
  2. Subtract that coin's value from what's left
  3. Repeat until you've made exact change

This "biggest first" strategy is the greedy choice: at each step, you make the locally optimal decision without worrying about future consequences.

When It Works

For standard coin systems (like US currency: 1¢, 5¢, 10¢, 25¢), this greedy method always gives the optimal answer. The coin denominations have a special mathematical property that guarantees this.

However, be aware: with unusual denominations (say, coins worth 1, 3, and 4), greedy doesn't always work. For amount 6, greedy picks 4 then two 1s (3 coins), but the optimal is two 3s (2 coins).

Example Walkthrough

Make change for 41¢ using quarters (25¢), dimes (10¢), nickels (5¢), pennies (1¢):

  • Pick 25¢ → remaining: 16¢
  • Pick 10¢ → remaining: 6¢
  • Pick 5¢ → remaining: 1¢
  • Pick 1¢ → remaining: 0¢

Total: 4 coins (1 quarter, 1 dime, 1 nickel, 1 penny)

Key Takeaway: The greedy coin-change algorithm repeatedly selects the largest denomination that fits, minimizing coin count for standard currency systems in linear time.