Minimum Number of Coins
This problem can be solved using the Greedy Approach.
Goal: Given various denominations of coins (with infinite supply of coins for each denomination), find the minimum number of coins required to get a sum of k
- Sort denominations in descending order
- Start with the highest denomination
- Keep choosing lower denominations as long as the sum<=required sum (we can choose multiple coins of the same denomination as well)
- Denominations: 25, 10, 5, 1
- Required sum: 31
Greedy Approach Output: 25, 5, 1 (3 coins)
Note: Greedy Approach may not always work optimally for this problem
Say we have denominations of 25, 10, 1 and we need sum=31
Greedy approach will give 7 coins as the result i.e. 25 and 6 1s. However, the optimal solution is 4 coins i.e. 3 10s and one 1.
Time Complexity: O(k) - worst case; k: required sum