A post office sells stamps in k distinct denominations, with an unlimited supply of each. Find the minimum number of stamps whose values sum to EXACTLY a target postage T. If it is impossible to make exactly T, print -1.
Line 1: two integers T k.
Line 2: k distinct space-separated positive integers, the stamp denominations.
A single integer: the minimum number of stamps summing to exactly T, or -1 if impossible. (If T = 0, the answer is 0.)
Example 1
Input
6 3 1 3 4
Expected
2
Explanation
Two 3-value stamps sum to 6, which is fewer stamps than any other combination: answer 2.
Example 2
Input
7 1 2
Expected
-1
Explanation
Only 2-value stamps are available, and 7 is odd, so exact postage of 7 is impossible: answer -1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →