Course launching November 17, 2020
Follow me on YouTube for free coding interview videos.
Users who sign up for the email list will receive an exclusive 75% discount at launch.
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
Assume you have as much of any available denomination needed to solve the problem.
const denominations = [1, 5, 10]; const targetChange = 12; minCoinsForChange(denominations, targetChange); // Output: 3 --> 1x10 + 2x1 const denominations = [5, 10, 25]; const targetChange = 53; minCoinsForChange(denominations, targetChange); // Output: -1
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 solved 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.lengthand
targetis the actual value of the target.