FastPrepCoin Change

Coin Change

Expedia logoExpedia● MediumNEW GRADINTERNONSITE INTERVIEW

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) → int

Examples

Example 1

coins = [1,2,5]amount = 11return = 3

Use 5 + 5 + 1.

Example 2

coins = [2]amount = 3return = -1

A sum of coins valued 2 cannot be odd.

Example 3

coins = [1]amount = 0return = 0

The 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

Similar questions at other companies

Interview reports that mention this question

Expedia interview experiences

All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public int coinChange(int[] coins, int amount) {
        // Write your solution here.
    }

}
Checking account…