# Vending Machine

## Course launching August 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 manage how we're handling change. We want to calculate minimum number of coins to add up to the change.

We this vending machine can be used anywhere in the world with any currency, so as an input, we'll also take the denominations available.

**Write a function minCoinsForChange that returns an integer for the smallest number of coins required to make change. If combination is possible, return -1.**

Assume you have as much of any coin as 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. I'll show the bottom-up approach.

This can be solved using dynamic programming. Store value of different coin combinations to yield a solution.

This can be solved in

*O(d x target)*, where`d = denominations.length`

and`target`

is the actual value of the target.