Minimum number of coins
Statement
Goal
Given a non-negative amount N and a set of coins of S positive values Vi, return the smallest number of coins that sum up to the required amount.NB : You have an unlimited amount of coin of each value at your disposal.
Input
Line 1 : A non-negative integer N for the target amount.
Line 2 : A non-negative integer S for the number of possible values coins.
Line 3 : S space-separated positive integers Vi for the value of the i-th coin.
Line 2 : A non-negative integer S for the number of possible values coins.
Line 3 : S space-separated positive integers Vi for the value of the i-th coin.
Output
An integer representing the minimum number of coins that sum up to N, or -1 if the target amount cannot be reached.
Constraints
0 <= N <= 1e8
0 <= S <= 50
0 < Vi <= 500
0 <= S <= 50
0 < Vi <= 500
Example
Input
3 2 1 2
Output
2
Tags
Dynamic programming
Difficulty
Easy
Test cases
Coins only Test
Input
3
2
1 2
Output
2
Do not use your bank notes Validator
Input
4
3
1 5 10
Output
4
Real-life change Test
Input
379
9
1 2 5 10 20 50 100 200 500
Output
7
Validator 2 Validator
Input
899
9
1 2 5 10 20 50 100 200 500
Output
9
How am I supposed to pay ?! Test
Input
152
0
Output
-1
Validator 3 Validator
Input
75
0
Output
-1
What is that money ?! Test
Input
856
25
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Output
10
Validator 4 Validator
Input
1243
25
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Output
13
Let's buy a Castle Test
Input
1527495
9
1 2 5 10 20 50 100 200 500
Output
3060
Validator 5 Validator
Input
1234555
6
1 2 10 50 100 500
Output
2473
Solution language
Solution
Stub generator input