Minimum Coins
The minimum coin change problem (for coin systems where greedy works, like Indian/US currency) aims to make change for a given amount using the fewest coins. Greedy: always take the largest coin not exceeding the remaining amount.
Note: Greedy works for canonical coin systems but not all. For arbitrary coins, DP is needed.
Java implementation (for standard denominations):
public static int minCoins(int[] coins, int amount) {
// coins sorted in descending order
int count = 0;
for (int coin : coins) {
if (amount >= coin) {
int num = amount / coin;
count += num;
amount -= num * coin;
}
}
return amount == 0 ? count : -1;
}
Greedy works for denominations like 1,2,5,10,20,50,100, etc. For arbitrary coin systems, dynamic programming is required.
Two Minute Drill
- Minimum coins problem: greedy works for canonical coin systems.
- Sort coins descending, take as many large coins as possible.
- For general coins, use dynamic programming.
- Greedy approach is simple and fast.
Need more clarification?
Drop us an email at career@quipoinfotech.com