MediumDpAI interview only
Coin Change
Asked atamazongooglemetamicrosoftgoldman-sachs
01 · Problem
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
02 · Examples
Example 01
Input
coins = [1,2,5], amount = 11
Output
3
11 = 5 + 5 + 1. Three coins is the minimum. Other combos like 2+2+2+2+2+1 use 6 coins.
Example 02
Input
coins = [2], amount = 3
Output
-1
No combination of coins with denomination 2 can sum to 3 (an odd number). Return -1.
03 · Constraints
- 011 <= coins.length <= 12
- 021 <= coins[i] <= 231 - 1
- 030 <= amount <= 104
04 · Optimal complexity
- Time
- O(amount * n)
- Space
- O(amount)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.