DSA interview question

Minimum Coins (Coin Change 1)

Hard · Algorithms · Topics: dynamic programming, unbounded knapsack

The problem

You're building the "optimal change dispenser" logic for a vending-machine network. Each machine stocks an unlimited supply of a fixed set of coin denominations, and to minimize mechanical wear (fewer coins dropped = less jamming risk), the machine should dispense change using the fewest coins possible. Given a coins array (unlimited supply of each denomination) and a target amount X, find the minimum number of coins needed to make up that amount. If it's impossible to make the amount with the given denominations, return -1.

Function signature

int minCoins(vector<int>& coins, int X);

Test cases

`coins`	`X`	Output	Explanation
`[1,2,5]`	11	3	5 + 5 + 1 = 11, using 3 coins
`[2]`	3	-1	impossible — can't make an odd amount using only 2s
`[1]`	0	0	zero amount needs zero coins
`[1]`	5	5	five 1-coins
`[]`	5	-1	no coins available, positive amount unreachable
`[]`	0	0	zero amount always achievable with zero coins, even with no coins available
`[3,7,10]`	14	2	7 + 7 = 14, using 2 coins (not 10+3+... which would need more coins)

(Key contrast to flag upfront: this is DIFFERENT from Coin Change 2 — that counted the number of combinations; this minimizes coin count. Same input shape, completely different DP transition.)

How interviewers phrase it

"Given coin denominations (unlimited supply) and a target amount, find the minimum number of coins needed to make that amount, or -1 if impossible."
"What's the fewest number of coins to make change for this amount?"
Often the very first unbounded-knapsack-flavored DP question asked, sometimes followed immediately by "Coin Change 2" to test whether you can tell min-count and count-of-combinations apart.

Clarifying questions to ask

Is each coin denomination available in unlimited supply? (Confirm — unbounded knapsack, not 0/1.)
What should be returned if the amount is unreachable? (Standard convention: -1.)
What should X = 0 return? (Standard convention: 0 — zero coins needed.)
Are coin values guaranteed positive? Could there be duplicates or a 0-valued coin in the array? (A 0-valued coin would be degenerate — infinite coins could theoretically be "added" without changing the sum, but wouldn't reduce coin count, so it's usually safe to ignore, but worth flagging.)
What's the expected range of X and number of coin denominations? (Signals whether O(coins × X) DP is acceptable.)

Follow-ups to expect

"How is this different from Coin Change 2 (counting combinations)?"
"Can you reconstruct which coins were actually used, not just the count?"
"Can you optimize space?"
"Why doesn't loop order (coins outer vs. amount outer) matter here, unlike Coin Change 2?"
"What if this needs to run for many different target amounts with the same coin set?"
"Is a greedy approach (always use the largest coin first) valid?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview