Skip to main content

25. Coin Change

mediumAsked at Unity

Find the minimum number of coins that sum to an amount — the same unbounded-knapsack DP Unity's animation system uses to compute the minimum number of transition clips needed to blend from one animator state to a target without over-spending frame budget.

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

Problem

You are given an integer array coins representing coin denominations and an integer amount. Return the fewest number of coins needed to make up that amount. If it cannot be made up by any combination of the coins, return -1. You may use each coin an unlimited number of times.

Constraints

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

Examples

Example 1

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

Explanation: 11+1+1+1 = 14? No — 11+4 doesn't work without a 4. 5+5+5 = 15 in 3 coins.

Example 2

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

Approaches

1. Recursive with memoization (top-down)

Recurse on amount - coin for each coin; memoize results. Returns 1 + min(subproblems).

Time
O(amount * coins.length)
Space
O(amount)
function coinChange(coins, amount) {
  const memo = new Map();
  function dp(rem) {
    if (rem < 0) return -1;
    if (rem === 0) return 0;
    if (memo.has(rem)) return memo.get(rem);
    let best = Infinity;
    for (const c of coins) {
      const sub = dp(rem - c);
      if (sub !== -1) best = Math.min(best, sub + 1);
    }
    const res = best === Infinity ? -1 : best;
    memo.set(rem, res);
    return res;
  }
  return dp(amount);
}

Tradeoff:

2. Bottom-up DP tabulation

Build dp[0..amount] where dp[a] = min coins for amount a. Transition: dp[a] = min(dp[a], dp[a-coin]+1) for each coin.

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

Tradeoff:

Unity-specific tips

Unity grades for recognizing this as unbounded knapsack, not bounded. Mention that the bottom-up table avoids recursion overhead, then connect it to how the Animator computes minimum-transition-step plans offline so runtime playback never re-solves it per frame.

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

Practice these live with InterviewChamp.AI →