# [Solved] Minimum Number of Coins Required to Make Given Amount

Problem Statement: You have been given a set of coins. Write a program to find the minimum number of coins required to match the given amount value.

#### Example

```You have coins 1, 5, 7, 9, 11. Calculate minimum number of coins required for any input amount 250.

Example:
AMount 6 will require 2 coins (1, 5).
Amount 25 will require 3 coins (5, 9, 11).```

This question was asked in the coding round of Byju’s interview.

You can use the Dynamic programming approach to solve this coding challenge.

#### Python Code

```def get_min_coin(coins, val) -> int:
if val < 0:
return -1
max_val = val + 1
min_coins = [max_val] * (val+1)
min_coins[0] = 0
for coin in coins:
for v in range(coin, val+1):
min_coins[v] = min(1 + min_coins[v-coin], min_coins[v])

return min_coins[-1]

print(get_min_coin([1, 2, 5], 18))```

Output

`5`

#### Explanation

`18 => 5 coins (3 coins of 5, 1 coin of 2, 1 coin of 1)`

Here min_coins[i] is a list of minimum coins required amount ‘i’. If you print min_coin, it will look like this.

```min_coins = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 3, 4, 4, 5]

min_coins[0] => 0
min_coins[1] => 1
min_coins[2] => 1
min_coins[3] => 2
.
.
.
min_coins[18] => 5```

If you understand the logic to calculate the minimum number of coins required, you can implement it in any programming language of your choice like C/C++, Java, etc.

Do you think any other approach to solve this problem? Let’s share it with us in the comment.