Coin Change
Updated
Problem statement
You are given distinct positive coin denominations coins and a nonnegative amount. There is an unlimited supply of each denomination.
Return the fewest coins needed to make the amount exactly, or -1 if it is impossible. An amount of zero needs zero coins.
Function
coinChange(coins: int[], amount: int) → intExamples
Example 1
coins = [1,2,5]amount = 11return = 3Use 5 + 5 + 1.
Example 2
coins = [2]amount = 3return = -1A sum of coins valued 2 cannot be odd.
Example 3
coins = [1]amount = 0return = 0The empty selection has total zero.
Constraints
1 <= coins.length <= 12.1 <= coins[i] <= 2147483647.0 <= amount <= 10000.- All denominations are distinct.
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
Similar questions at other companies
- Count Subsets With a Target SumSafe Security · ONSITE INTERVIEW
- 0/1 Knapsack with Weight and Volume LimitsGoogle · ONSITE INTERVIEWGoogle interview questions
- Maximum Subarray Sum with One DeletionOracle · ONSITE INTERVIEWOracle interview questions
- Best Time to Buy and Sell Stock IIKotak Mahindra Bank · ONSITE INTERVIEWKotak Mahindra Bank interview questions
- Coin ChangeMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Word BreakAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Maximum SubarrayUpstart · ONSITE INTERVIEWUpstart interview questions
- Maximum Product SubarrayHartford Financial Services · ONSITE INTERVIEWHartford Financial Services interview questions
- Word BreakMoveworks · ONSITE INTERVIEWMoveworks interview questions
- Maximum Value from Circular HousesDigitalOcean · ONSITE INTERVIEWDigitalOcean interview questions