hardDynamic Programming 1DIndian domain~30 min
Fewest Currency Notes to Settle an Exact Amount
A payouts service settles an exact rupee amount using available note denominations (unlimited supply of each). Find the minimum number of notes needed, or report that the amount cannot be settled exactly.
Problem
Given an array denominations of distinct positive note values (unlimited supply each) and an integer amount in rupees, return the minimum number of notes summing exactly to amount, or -1 if it cannot be made.
Input
An array denominations and an integer amount.
Output
An integer: the minimum number of notes, or -1.
Constraints
- 1 <= denominations.length <= 12
- 1 <= denominations[i] <= 2000 (e.g. 1, 2, 5, 10, 20, 50, 100, 200, 500)
- 0 <= amount <= 10^4
Examples
Example 1
Input
denominations = [1,2,5], amount = 11
Output
3
5 + 5 + 1 uses three notes.
Example 2
Input
denominations = [2], amount = 3
Output
-1
An odd amount cannot be made from 2-rupee notes.