Asked at
Coin Change
MediumVerifiedArrayDynamic Programming~25 min
Given coin denominations coins and a target amount, return the fewest coins needed to make amount. Each coin may be used unlimited times. Return -1 if it cannot be made.
The input arrives as a single object { coins, amount }. Return the count.
Examples
in{ coins: [1, 2, 5], amount: 11 }
out3
5 + 5 + 1 = 11.
in{ coins: [2], amount: 3 }
out-1
No combination of 2s makes 3.
Constraints
- 1 ≤ coins.length ≤ 12
- 1 ≤ coins[i] ≤ 2³¹ − 1
- 0 ≤ amount ≤ 10⁴
- Target: O(amount · coins) time
Get help
🔑
Sign in to solve
Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.