GreedyProblem 6 of 35
Greedy Algorithm to find Minimum number of Coins
Problem Statement
Given a value V and infinite supply of coins with denominations {c1, c2, ..., cn}, find the minimum number of coins needed to make change for V. If the coin system is canonical (like standard currency), greedy works optimally.
Note: Greedy works for canonical coin systems (like Indian/US currency). For arbitrary coin systems, use Dynamic Programming.
Constraints:
- 1 ≤ V ≤ 10^9
- 1 ≤ n ≤ 10
- Coins are in canonical system
Example:
- Input:
V = 93,coins = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000](Indian currency) - Output:
5coins (50 + 20 + 20 + 2 + 1)
Example 2:
- Input:
V = 11,coins = [1, 5, 6, 9] - Output: Greedy gives
3(9 + 1 + 1), but optimal is2(5 + 6) - Note: This is a non-canonical system where greedy fails!
Approach 1: Brute Force (Recursion)
Intuition
Try all possible combinations of coins and find the minimum number needed.
Algorithm
- For each coin denomination, try using 0, 1, 2, ... coins
- Recursively solve for remaining amount
- Track minimum coins used
java
import java.util.*;
public class Solution {
private int minCoins = Integer.MAX_VALUE;
private void solve(int[] coins, int amount, int count) {
if (amount == 0) {
minCoins = Math.min(minCoins, count);
return;
}
if (amount < 0) return;
for (int coin : coins) {
if (coin <= amount) {
solve(coins, amount - coin, count + 1);
}
}
}
public int findMinCoins(int[] coins, int V) {
minCoins = Integer.MAX_VALUE;
solve(coins, V, 0);
return minCoins == Integer.MAX_VALUE ? -1 : minCoins;
}
}Complexity Analysis
- Time Complexity: O(amount^n) - Exponential, trying all combinations
- Space Complexity: O(amount) - Recursion stack depth
Approach 2: Greedy (For Canonical Systems) - Optimal
Intuition
For canonical coin systems, always using the largest coin that doesn't exceed the remaining amount gives the optimal solution.
Why it works for canonical systems: Canonical systems are designed so that using larger coins first is always optimal. For example, in Indian currency, 2×50 = 100, so using one 100 coin is never worse than two 50 coins.
Algorithm
- Sort coins in descending order
- Start with the largest coin
- Use as many of that coin as possible
- Move to the next smaller coin
- Repeat until amount becomes 0
java
import java.util.*;
public class CoinChange {
public int[] findMinCoins(int[] coins, int V) {
// Sort in descending order
Integer[] sortedCoins = Arrays.stream(coins).boxed().toArray(Integer[]::new);
Arrays.sort(sortedCoins, Collections.reverseOrder());
List<Integer> result = new ArrayList<>();
int remaining = V;
for (int coin : sortedCoins) {
if (remaining == 0) break;
// Use as many of this coin as possible
int numCoins = remaining / coin;
if (numCoins > 0) {
remaining -= numCoins * coin;
for (int i = 0; i < numCoins; i++) {
result.add(coin);
}
}
}
if (remaining != 0) {
return new int[]{-1};
}
return result.stream().mapToInt(i -> i).toArray();
}
public void printBreakdown(int[] coins, int V) {
int[] coinList = findMinCoins(coins, V);
if (coinList.length == 1 && coinList[0] == -1) {
System.out.println("Cannot make change for " + V);
return;
}
System.out.println("Value: " + V);
System.out.println("Total coins: " + coinList.length);
// Group coins
Map<Integer, Integer> coinCount = new TreeMap<>(Collections.reverseOrder());
for (int coin : coinList) {
coinCount.merge(coin, 1, Integer::sum);
}
System.out.println("Breakdown:");
for (Map.Entry<Integer, Integer> entry : coinCount.entrySet()) {
System.out.printf(" %d x %d = %d%n",
entry.getKey(), entry.getValue(),
entry.getKey() * entry.getValue());
}
}
public static void main(String[] args) {
CoinChange cc = new CoinChange();
int[] coins = {1, 2, 5, 10, 20, 50, 100, 200, 500, 2000};
cc.printBreakdown(coins, 93);
System.out.println();
cc.printBreakdown(coins, 2589);
}
}Dry Run Example
coins = [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]
V = 93
After sorting (descending):
[2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
Step 1: coin = 2000
93 / 2000 = 0, skip
Step 2: coin = 500
93 / 500 = 0, skip
Step 3: coin = 200
93 / 200 = 0, skip
Step 4: coin = 100
93 / 100 = 0, skip
Step 5: coin = 50
93 / 50 = 1
remaining = 93 - 50 = 43
result = [50]
Step 6: coin = 20
43 / 20 = 2
remaining = 43 - 40 = 3
result = [50, 20, 20]
Step 7: coin = 10
3 / 10 = 0, skip
Step 8: coin = 5
3 / 5 = 0, skip
Step 9: coin = 2
3 / 2 = 1
remaining = 3 - 2 = 1
result = [50, 20, 20, 2]
Step 10: coin = 1
1 / 1 = 1
remaining = 1 - 1 = 0
result = [50, 20, 20, 2, 1]
Result: 5 coins
Breakdown: 50×1 + 20×2 + 2×1 + 1×1 = 50 + 40 + 2 + 1 = 93
Complexity Analysis
- Time Complexity: O(n) where n is the number of coin denominations
- O(n log n) if sorting is needed
- O(n) for iterating through coins
- Space Complexity: O(1) if we only count, O(V/min_coin) if storing coins
When Greedy Fails
For non-canonical coin systems, greedy may not give optimal results:
Key Takeaways
- Canonical Systems: Greedy works for standard currency systems
- Largest First: Always use the largest coin that fits
- Non-Canonical: Use DP for arbitrary coin systems
- Greedy Choice: Pick largest coin ≤ remaining amount
- O(n) Complexity: Very efficient for canonical systems
- Real Applications: ATM cash dispensing, change making
- Verification: For new coin systems, verify greedy gives optimal
- DP Backup: When unsure, DP always gives correct answer