How should I practice Coin Change?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft onsite interview problems in FastPrep.

Is Coin Change associated with Microsoft?

FastPrep tags this as a Microsoft onsite interview coding practice problem when the problem catalog has that company and stage context.

Coin Change

Microsoft● MediumFULLTIMEONSITE INTERVIEW

Problem statement

You are given an integer array coins, where each value is the worth of one kind of coin, and an integer amount. You have an unlimited number of coins of every kind.

Return the fewest number of coins whose values add up to exactly amount. If no combination of coins adds up to amount, return -1.

A total of 0 needs no coins. A value may appear more than once in coins; repeated values are the same kind of coin.

Function

coinChange(coins: int[], amount: int) → int

Examples

Example 1

coins = [2,5,10]amount = 27return = 4

One way to make 27 with four coins is 10 + 10 + 5 + 2.

Three coins are not enough. The total 27 is odd, and 5 is the only odd coin, so at least one 5 is used. The other two coins would then have to add up to 22, but two coins add up to at most 10 + 10 = 20. So the answer is 4.

Example 2

coins = [1,3,4]amount = 6return = 2

Two coins work: 3 + 3 = 6. One coin is not enough, because no coin is worth 6.

Always taking the largest coin first gives 4 + 1 + 1, which uses three coins, so a greedy choice does not give the fewest coins here.

Example 3

coins = [4,6]amount = 9return = -1

Every coin value is even, so any combination of these coins adds up to an even total. The total 9 is odd, so it cannot be made, and the answer is -1.

Example 4

coins = [7]amount = 0return = 0

A total of 0 needs no coins, so the answer is 0.

Constraints

1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4