577. King's Gold Coin Reward
0
Medium
King Andrew, the ruler of a kingdom, rewards people with gold coins for their good deeds. He wants to reward them with the fewest number of coins possible. However, his smartest minister, Drake, is currently unavailable. Therefore, you have been tasked with helping the king in this endeavor.
You are given an array called 'coins' which represents different denominations of coins, and an integer called 'amount' which represents the total amount of money to be rewarded.
Your task is to determine the fewest number of coins needed to make up the given amount. If it is not possible to make up the amount using any combination of the coins, you should print -1.
You can assume that you have an infinite number of each kind of coin.
Input Format
The first line contains the size of the array.
The second line contains the elements of the array.
The third line contains the target amount.
Output Format
Print the fewest number of coins required to reach the target value.
Example
Input
3
1 2 5
11
Output
3
Constraints
1 <= arr.length <= 12
1 <= arr[i] <= 231 - 1
0 <= amount <= 104
1 <= arr[i] <= 231 - 1
0 <= amount <= 104
Loading...
View Submissions
Console