Skip to main content

21. Coin Change

mediumAsked at Adyen

Return the fewest coins needed to make an amount, or -1 if impossible.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an integer array of coin denominations and an integer amount, return the fewest number of coins needed to make up that amount. If it cannot be made, return -1.

Constraints

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4

Examples

Example 1

Input
coins = [1,2,5], amount = 11
Output
3

Example 2

Input
coins = [2], amount = 3
Output
-1

Approaches

1. Recursive brute force

Try every coin at every step.

Time
O(c^amount)
Space
O(amount)
function help(rem) {
  if (rem < 0) return -1;
  if (rem === 0) return 0;
  let best = Infinity;
  for (const c of coins) {
    const r = help(rem - c);
    if (r >= 0) best = Math.min(best, r + 1);
  }
  return best === Infinity ? -1 : best;
}

Tradeoff:

2. Bottom-up DP

dp[i] = fewest coins to make i; fill from 1 to amount.

Time
O(amount * coins)
Space
O(amount)
function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const c of coins) {
      if (c <= i) dp[i] = Math.min(dp[i], dp[i - c] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff:

Adyen-specific tips

Adyen reads this as a settlement-denomination problem — multi-currency payout rounding maps to picking the minimum-coin breakdown, and they grade the impossibility return path strictly.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Coin Change and other Adyen interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →