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.