Skip to main content

21. Coin Change

mediumAsked at Revolut

Find the minimum number of coins to make a target amount with unlimited supply, a Revolut staple that mirrors choosing the minimum number of pre-funded liquidity buckets to satisfy a payout.

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

Problem

Given an integer array coins of 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. Plain recursion

Try every coin at every step; return min coin count.

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

Tradeoff:

2. Bottom-up DP

dp[i] = fewest coins to reach amount i; dp[i] = min(dp[i-c]+1) for each coin c. Returns -1 if dp[amount] stayed at Infinity.

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 (i - c >= 0) dp[i] = Math.min(dp[i], dp[i-c]+1);
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff:

Revolut-specific tips

Revolut frames this as a payout-bucket selection problem — they want you to mention that real liquidity systems use integer minor units to avoid the floating-point comparison bugs that wreck DP solutions.

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 Revolut interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →