Ways to pay with a limited supply
You hold counts[i] coins of value coins[i] (values distinct). Return the number of different
combinations, as a multiset of coins, that pay exactly amount. Paying 0 has one way.
Examples
| Input | Output | Why |
|---|---|---|
coins = [1,2,5], counts = [3,2,1], amount = 5 | 3 | 5; 2 + 2 + 1; 2 + 1 + 1 + 1. |
coins = [1,2], counts = [2,2], amount = 4 | 2 | 2 + 2; 2 + 1 + 1. |
coins = [3], counts = [1], amount = 6 | 0 | Only one 3. |
Constraints
- 1 ≤ coins.length ≤ 50
- 1 ≤ counts[i] ≤ 1000
- 0 ≤ amount ≤ 10⁴
- The answer fits in a 64-bit integer
Hints
Hint 1
ways[t] after coin i = Σ over k = 0..counts[i] of old ways[t − k · c].
Hint 2
That sum slides: it is the previous term for t − c plus old[t] minus old[t − (counts + 1) · c].
Hint 3
Binary splitting into bundles overcounts: two bundle choices can give the same number of coins.
Where people lose marks
- Binary splitting the supply, which overcounts.
- Forgetting to subtract the term that falls out of the window.
- Counting ordered sequences instead of combinations.
Dry run on [1,2,5],[3,2,1],5
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 4ways100102030405
One way to pay 0.
-
Step 2 / 4ways101112130405
Allow up to 3 × 1: each total sums the old ways at t, t − 1, …, t − 3.
-
Step 3 / 4ways101122232425
Allow up to 2 × 2: each total sums the old ways at t, t − 2, …, t − 4.
-
Step 4 / 4ways101122232435
Allow up to 1 × 5: each total sums the old ways at t, t − 5, …, t − 5. ways[5] = 3.
How to think about it
Process coins one at a time. With coin c available k times, the number of ways to pay t is the sum of the old ways for
t, t − c, t − 2c, …, t − k·c. Computed naively that is O(k) per total. The sums for t and t − c overlap in all but two
terms, so new[t] = new[t − c] + old[t] − old[t − (k + 1)c] (dropping terms with negative index). That makes each
coin O(amount). Binary splitting, which works for min and max, would count the same multiset several times here.
Complexity. Time O(coins · amount) · Space O(amount)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def ways_limited(coins, counts, amount):
ways = [1] + [0] * amount
for c, k in zip(coins, counts):
new = [0] * (amount + 1)
for t in range(amount + 1):
new[t] = ways[t] # use none of this coin
if t >= c:
new[t] += new[t - c] # sliding sum of ways[t - c], ways[t - 2c], ...
if t >= (k + 1) * c:
new[t] -= ways[t - (k + 1) * c] # ... but at most k coins
ways = new
return ways[amount]#include <vector>
long long solve(const std::vector<int>& coins, const std::vector<int>& counts, int amount) {
std::vector<long long> ways(amount + 1, 0), next(amount + 1);
ways[0] = 1;
for (size_t i = 0; i < coins.size(); ++i) {
long long c = coins[i], drop = (long long)(counts[i] + 1) * c;
for (int t = 0; t <= amount; ++t)
next[t] = ways[t] + (t >= c ? next[t - c] : 0) - (t >= drop ? ways[t - drop] : 0); // window of k + 1 terms
ways.swap(next);
}
return ways[amount];
}class Solution {
public long waysLimited(int[] coins, int[] counts, int amount) {
long[] ways = new long[amount + 1], next = new long[amount + 1];
ways[0] = 1;
for (int i = 0; i < coins.length; i++) {
long c = coins[i], drop = (long) (counts[i] + 1) * c;
for (int t = 0; t <= amount; t++)
next[t] = ways[t] + (t >= c ? next[(int) (t - c)] : 0) - (t >= drop ? ways[(int) (t - drop)] : 0);
long[] tmp = ways; ways = next; next = tmp;
}
return ways[amount];
}
}function waysLimited(coins, counts, amount) {
let ways = [1, ...new Array(amount).fill(0)];
for (let i = 0; i < coins.length; i++) {
const c = coins[i], drop = (counts[i] + 1) * c, next = new Array(amount + 1).fill(0);
for (let t = 0; t <= amount; t++) {
next[t] = ways[t] + (t >= c ? next[t - c] : 0) - (t >= drop ? ways[t - drop] : 0); // sliding window of k + 1 terms
}
ways = next;
}
return ways[amount];
}fn solve(coins: &[i64], counts: &[i64], amount: i64) -> i64 {
let n = amount as usize;
let mut ways = vec![0i64; n + 1];
ways[0] = 1;
for (i, &c) in coins.iter().enumerate() {
let (c, drop) = (c as usize, ((counts[i] + 1) * c) as usize);
let mut next = vec![0i64; n + 1];
for t in 0..=n {
next[t] = ways[t];
if t >= c {
next[t] += next[t - c]; // sliding sum
}
if t >= drop {
next[t] -= ways[t - drop]; // at most k coins
}
}
ways = next;
}
ways[n]
}solve :: [Int] -> [Int] -> Int -> Int
solve coins counts amount = foldl addCoin (1 : replicate amount 0) (zip coins counts) !! amount
where
-- new[t] = old[t] + new[t - c] - old[t - (k + 1)c]: a sliding sum of k + 1 old terms
addCoin old (c, k) = new
where
new = zipWith3 (\o prevNew dropped -> o + prevNew - dropped) old (replicate c 0 ++ new) (replicate ((k + 1) * c) 0 ++ old)Variants to try
- Answer modulo 10⁹ + 7.
- The fewest coins instead (the previous problem).
- Each coin also has a weight limit: add a dimension.
Next problems
The fewest coins from a limited supply
Pay an amount with the fewest coins when you hold only so many of each. Binary-split the supply into bundles and run a 0/1 knapsack with min.
Open the problem → Easy10 minThe cheapest way up a staircase
Each step has a cost; climb one or two steps at a time; start on step 0 or 1. Return the cheapest way past the top.
Open the problem → Medium15 minCan a subset reach the target?
Decide whether some subset of positive integers adds up to exactly the target. A boolean array over totals, filled downwards for each number.
Open the problem →Write a solution and run it against the real test table.
Keep going
The fewest coins from a limited supply
Pay an amount with the fewest coins when you hold only so many of each. Binary-split the supply into bundles and run a 0/1 knapsack with min.
Open the problem → Easy10 minThe cheapest way up a staircase
Each step has a cost; climb one or two steps at a time; start on step 0 or 1. Return the cheapest way past the top.
Open the problem → Medium15 minCan a subset reach the target?
Decide whether some subset of positive integers adds up to exactly the target. A boolean array over totals, filled downwards for each number.
Open the problem → Dynamic programmingThe pattern behind it
Write the recursion, notice the repeats, fill a table in an order that makes each entry final.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.