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:
- Always pick the largest coin that doesn't exceed your remaining amount
- Subtract that coin's value from what's left
- 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.