Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

164. Coin Change

MediumDay 48 of 60Dynamic Programming

You have coins of the denominations in coins (an unlimited supply of each) and a target amount. Return the fewest number of coins that add up to exactly amount, or -1 if it cannot be made. Making amount 0 needs 0 coins.

Example 1
Input: coins = [1,2,5], amount = 11
Output: 3
11 = 5 + 5 + 1.
Example 2
Input: coins = [2], amount = 3
Output: -1
Constraints
  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4
Hints
Frequently asked at: Amazon, Google, Microsoft, Goldman Sachs, Paytm
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min