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

Problem Statement: You have 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 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 languages of your choice like C/C++, Java.

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