ATM Minimum Notes To Dispense
An Indian bank ATM stocks notes in fixed denominations (₹100, ₹200, ₹500, ₹2000). For a requested withdrawal amount, dispense it using the fewest possible notes — and report when the amount cannot be made up exactly from the available denominations.
Problem
Given an array of note denominations and a target amount, return the minimum number of notes that sum exactly to the amount. Each denomination may be used any number of times. If the amount cannot be formed, return −1.
Input
An array denominations (1 ≤ length ≤ 12) of distinct positive ints, and amount (0 ≤ amount ≤ 100000).
Output
An integer — minimum note count, or −1 if impossible.
Constraints
- Each denomination is reusable without limit
- Amount 0 needs 0 notes
- Denominations are not guaranteed to be 'canonical', so greedy can fail
Examples
Example 1
Input
denominations = [100,200,500,2000], amount = 2300
Output
3
2300 = 2000 + 200 + 100, three notes — the fewest possible.
Example 2
Input
denominations = [100,500], amount = 300
Output
3
Only ₹100 notes can form 300 → three notes; ₹500 overshoots.