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

Algorithm:

1. Sort denominations in descending order

2. Start with the highest denomination

3. Keep choosing lower denominations as long as the sum<=required sum (we can choose multiple coins of the same denomination as well)

Example:

• 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