Loading...
Loading...
Loading...
Pooja runs the change counter at the pickup desk of an online store. The counter has coins of n different values, and there are as many coins of each value as she needs.
A student must get back exactly amount rupees. Print the fewest coins that add up to exactly that amount. If no mix of coins makes the amount, print -1.
-1.Example 1
Input
3 1 2 5 11
Output
3
Two 5s and one 1 make 11 with 3 coins.
Example 2
Input
1 2 3
Output
-1
Only 2-rupee coins: every total is even, so 3 cannot be made.
Try the problem first. Open one hint at a time.
Let fewest[a] be the fewest coins that make exactly a rupees. fewest[0] = 0.
The last coin used for amount a is one of the n values c. Then fewest[a] = 1 + fewest[a - c] for the best choice of c.
Fill the table from a = 1 up to the amount. Mark amounts that cannot be made with a value bigger than any real answer, such as amount + 1.
Taking the biggest coin first does not always work.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor