Skip to main content

22. Coin Change

mediumAsked at Intuit

Given coin denominations and a target amount, find the fewest coins needed to make the amount. Intuit asks this constantly — it maps directly to giving change in QuickBooks POS and to optimal-payment-plan calculations in TurboTax.

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

Source citations

Public interview reports confirming this problem appears in Intuit loops.

  • Glassdoor (2026-Q1)— Intuit POS team onsite — coin change framed as 'minimal-tender breakdown.'
  • LeetCode Discuss (2025-10)— TurboTax SWE II loop — coin change with non-canonical denominations.
  • Blind (2025-09)— Intuit interview prep guide explicitly lists Coin Change as a top-10 problem.

Problem

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.

Constraints

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4
  • Use integer cents — no floats.

Examples

Example 1

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

Explanation: 11 = 5 + 5 + 1.

Example 2

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

Explanation: Cannot make 3 from only 2s.

Example 3

Input
coins = [1], amount = 0
Output
0

Approaches

1. Greedy (broken)

Always take the largest coin that fits. Works for USD canonical denominations but fails on non-canonical sets.

Time
O(amount)
Space
O(1)
function coinChange(coins, amount) {
  coins.sort((a, b) => b - a);
  let count = 0;
  for (const c of coins) {
    while (amount >= c) { amount -= c; count++; }
  }
  return amount === 0 ? count : -1;
}

Tradeoff: Fails on coins=[1,3,4], amount=6 (greedy: 4+1+1=3 coins; optimal: 3+3=2 coins). Mention and reject.

2. Bottom-up DP (optimal)

dp[i] = fewest coins to make amount i. Transition: dp[i] = 1 + min(dp[i - c]) over all coins c <= i. Base: dp[0] = 0.

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

Tradeoff: Polynomial. Use INF = amount + 1 as a sentinel because using Infinity confuses some IEEE-arithmetic edge cases.

Intuit-specific tips

Intuit cares deeply about this — their cash-register product literally computes change every transaction. They explicitly probe whether you'd reach for greedy first (and why it fails on non-canonical denominations). They grade for whether you treat amount as integer cents, NEVER as a float. Bonus signal: discuss Coin Change II (count combinations, LC 518) and mention that the 1D vs 2D DP iteration order matters there.

Common mistakes

  • Using greedy on non-canonical denominations like [1,3,4] and accepting the wrong answer.
  • Treating amounts as floats (e.g., 0.30) and accumulating floating-point error.
  • Returning dp[amount] when it's still Infinity instead of -1.

Follow-up questions

An interviewer at Intuit may pivot to one of these next:

  • Coin Change II — count the number of ways to make the amount (LC 518).
  • Print one optimal change set, not just the count.
  • What if some coins are limited in quantity? (Bounded knapsack.)

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

When does greedy work?

Greedy works when the coin system is canonical — every amount's optimal solution always includes the largest fitting coin. USD coins (1, 5, 10, 25) are canonical. Sets like [1, 3, 4] are not. The DP solution is denomination-agnostic.

Why integer cents instead of floats?

IEEE-754 doubles can't represent 0.10 exactly; subtracting 0.10 repeatedly accumulates drift. Integer cents (or 4-decimal micro-units for FX) avoid the issue entirely. Intuit interviewers will dock you for using floats on money.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →