Vending Machine
We're writing code for a vending machine and want to manage how we're handling change returned from payments. We want to calculate the minimum number of coins to add up to a customer's change.
This vending machine could be used anywhere in the world with any currency, so as an input, we'll also provide the denominations of coins available for change.
Write a function minCoinsForChange that returns an integer for the smallest number of coins required to make change. If a combination is not possible, return -1.
Assume you have as much of any available denomination needed to solve the problem.
Breakdown
Approach and test strategy
Minimum-coin dynamic programming with an unreachable sentinel
Read the approach, boundary cases, and complexity
Find the fewest available coins whose values total the requested amount, allowing denominations to be reused. For each amount, compare reachable smaller amounts plus one coin. Keep unreachable states distinct from a valid zero-coin result. Choosing the largest coin first is not generally correct: a denomination system can make a smaller initial choice lead to fewer coins or the only reachable answer.
Cases to check
- Return minus one when no denomination combination reaches the target.
- Use coins [2, 3] and amount eight, which needs three coins.
- Try a target below every denomination and a case where several combinations compete.
Cost model
A table over amounts zero through A with c denominations takes O(A · c) time and O(A) auxiliary storage. This bound depends on the numeric amount, so it is pseudo-polynomial in a binary-encoded amount.
Programming languages for this lesson
Starter code and reference implementations are available in:
The editor shows which of these languages can run on this deployment.
Validate My Answer
This can be solved either bottom-up or top-down. In either case, the solutions are reasonable, so go with what you're most comfortable with.
This can be completed using dynamic programming. You can solve subproblems and use memoization to build up your solution.
This can be solved in O(d x target), where
d = denominations.lengthandtargetis the actual value of the target.
Vending Machine
We're writing code for a vending machine and want to manage how we're handling change returned from payments. We want to calculate the minimum number of coins to add up to a customer's change.
This vending machine could be used anywhere in the world with any currency, so as an input, we'll also provide the denominations of coins available for change.
Write a function minCoinsForChange that returns an integer for the smallest number of coins required to make change. If a combination is not possible, return -1.
Assume you have as much of any available denomination needed to solve the problem.