Given a set of coins arr[] and amount , Write a program to find the minimum number of coins to make the change of given amount.

Problem Note

  • There are m number of different coin types available arr[] = [C1, C2, … Cm] . Here, arr is an array of integers representing available denominations.
  • We have an infinite supply of each type of coin.
  • The order of coins doesn’t matter.
  • If that amount cannot be made up by any combination of the coins, return -1.

Example 1 

Input: arr[] = [1, 2, 3, 4] , amount = 11 
Output: 3  
Explanation: We can use two coins of 4 cents and one coin of 3 cents i.e. 11 = 4 + 4 + 3


Example 2 

Input: arr[] = [3, 4] , amount = 5 
Output: -1 
Explanation: Amount 5 cannot be made up by any combination of the coins.