Vending Machine Coin Mixes
An old vending machine in a train station takes only a few kinds of coins and gives no change, so you must pay the exact price. A drink costs 30 cents and the machine accepts 5, 10 and 25 cent coins. You could pay with six 5s, or three 10s, or a 25 and a 5, and so on.
The order you drop coins in does not matter: a 25 then a 5 is the same handful as a 5 then a 25. How many different handfuls of coins pay exactly the price?
Your task
Write countMixes(coins, price). coins lists the accepted coin values, and you have as many of each as you need. Return how many different handfuls add up to exactly price. Two handfuls are the same if they contain the same number of each coin value.
A price of 0 has exactly one handful: no coins at all. If the price cannot be paid, return 0.
countMixes(coins: int[], price: int) → int
Examples
coins = [5, 10, 25] price = 30
5
The handfuls are: six 5s; one 10 and four 5s; two 10s and two 5s; three 10s; one 25 and one 5. That is 5.
coins = [2, 3] price = 7
1
Only 2 + 2 + 3 works. Counting orders would give 3 (2-2-3, 2-3-2, 3-2-2), but those are all the same handful.
Constraints
- 1 ≤ coins.length ≤ 10
- 1 ≤ coins[i] ≤ 500, all values different
- 0 ≤ price ≤ 500
- The answer is below 10¹⁵.
Start with brute force
Recursively choose how many of each coin to use, and count the choices that hit the price. With a 1-cent coin and many coin types, the number of handfuls itself can be in the trillions, and the recursion visits every one of them.
The same question, like "how many ways to pay 40 cents with only 5s and 10s", comes up again and again inside that recursion. A table answers each such question once.
Hints
0 of 4 shown- Hint 1
In the second example, a careless count finds 3 answers for one handful, because it counts 2-2-3 and 3-2-2 separately. How could you make sure each handful is built in only one order?
- Hint 2
Decide coin types one at a time, in a fixed order. First decide how many 5s, then how many 10s, then how many 25s. Each handful then has exactly one way to be built.
- Hint 3
Keep an array
ways[a]= number of handfuls that pay exactlyausing only the coin types handled so far. Start withways[0] = 1and zeros elsewhere. How does adding one new coin typecchange it? - Hint 4
For each coin type
c(outer loop), go through amountsafromcup toprice(inner loop) and doways[a] += ways[a - c]. Going upward lets a handful use the new coin several times. Swapping the two loops counts orders instead of handfuls.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
The danger is counting the same handful in several orders. Fix the order of decisions: bring in coin types one by one. After processing a coin type, ways[a] counts handfuls for a made only from the types so far. Every handful is built in exactly one way.
Trace coins [2, 3], price 7. Amounts 0 to 7:
- Start:
[1, 0, 0, 0, 0, 0, 0, 0]. Only price 0 can be paid, with nothing. - Add 2s. For a = 2..7,
ways[a] += ways[a - 2]:[1, 0, 1, 0, 1, 0, 1, 0]. Even amounts have one handful of all 2s. - Add 3s. a = 3: += ways[0] → 1. a = 4: += ways[1] → 1. a = 5: += ways[2] → 1. a = 6: += ways[3], which is already 1 → 2. a = 7: += ways[4] → 1.
Result: ways[7] = 1 (2 + 2 + 3), and ways[6] = 2 (2 + 2 + 2 and 3 + 3). Going upward inside the 3-coin pass is what allowed 3 + 3: ways[3] already included one 3 when ways[6] read it.
function countMixes(coins, price) {
// ways[a] = handfuls that pay exactly a, using the coin types seen so far
const ways = new Array(price + 1).fill(0);
ways[0] = 1;
for (const c of coins) { // one coin type at a time
for (let a = c; a <= price; a++) {
ways[a] += ways[a - c]; // add one more coin c to a handful for a - c
}
}
return ways[price];
}def count_mixes(coins, price):
# ways[a] = handfuls that pay exactly a, using the coin types seen so far
ways = [1] + [0] * price
for c in coins: # one coin type at a time
for a in range(c, price + 1):
ways[a] += ways[a - c] # add one more coin c to a handful for a - c
return ways[price]Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.