Fewest bills: hints, no solution
Easy · Greedy
A farm stand pays out cash from a till that holds an unlimited supply of bills in a few denominations. The denominations are given in any order, and they form a chain: once sorted, every denomination divides the next larger one exactly (for example 1, 5, 10, 50). Given an amount, return the fewest bills that add up to exactly that amount, or -1 if the amount cannot be paid exactly. An amount of 0 needs 0 bills.
Examples
- Input
- bills = [10, 1, 5, 50], amount = 87
- Output
- 7
- Note
- 50 + 10 + 10 + 10 + 5 + 1 + 1 uses 7 bills, and no combination uses fewer.
- Input
- bills = [2, 10, 20], amount = 7
- Output
- -1
- Note
- Every bill is even, so an odd amount cannot be paid.
- Input
- bills = [3, 6, 12], amount = 36
- Output
- 3
Constraints
- 1 <= bills.length <= 12, all denominations distinct and between 1 and 1000000
- After sorting, each denomination divides the next larger one
- 0 <= amount <= 1000000000
Hint 1: a nudge
Suppose you must pay the amount with just one kind of bill first. Which bill would you like to use as many times as possible, and why?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.