You are coding as a Guest. Sign in with your RoleNest account to permanently track your streak, earn XP, and climb the Campus Leaderboard!
Sign In with RoleNestProblem Set
🔥Coin Change: Minimum Denomination DPMedium
DAILY PROBLEM OF THE DAY+50 XP • Daily Streak
Solve today's challenge or tackle one of the 3 Super Hard challenges for +150 XP.
MediumDynamic Programming•Acceptance: 43.7%
Coin Change: Minimum Denomination DP
Targeted in FAANG & Tech OA:AmazonMicrosoftSwiggyUber
Real-World Engineering Context
Micro-transaction change-making algorithms in Stripe/Cashfree billing gateways and optimal network MTU packet fragmentation.
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.
Sample Test Cases
Input: [[1,2,5],11]
Expected: 3
Input: [[2],3]
Expected: -1
Input: [[1],0]
Expected: 0
Constraints
- 1 <= coins.length <= 12
- 1 <= coins[i] <= 2^31 - 1
- 0 <= amount <= 10^4
Recruiter Fast-Track ReferralVerified Candidate
Direct pipeline to Google, Amazon, Microsoft, Swiggy, & Uber recruiters
Top DevScore profiles bypass resume screening filters. Every verified problem solve writes authentic proof-of-work to your profile and dispatches you directly into employer inboxes on RoleNest.
Explore 5,000+ Direct ATS Openings on RoleNest ↗✓ Direct Referral Active
Language:
Ready to test. Click Run Code or Submit Solution to run test cases in isolated browser sandbox.