# 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**:

- 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)

**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