Skip to main content

84. Coin Change

mediumAsked at Workday

Find the minimum number of coins to make a target amount. Workday uses this for unbounded-knapsack DP — same shape as allocating the minimum number of pay-frequency cycles to reach a target year-to-date amount.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025-Q4)— Workday SDE2 onsite — DP staple.

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

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

Example 3

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

Approaches

1. Greedy take largest coin

Sort coins desc; take largest possible.

Time
O(n)
Space
O(1)
// fails on coins=[1,3,4], amount=6 — greedy gives 4+1+1=3, optimal is 3+3=2

Tradeoff: Greedy doesn't work for arbitrary coin sets.

2. Bottom-up DP

dp[i] = min coins to make amount i. dp[i] = min over coins c of dp[i - c] + 1.

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 i = 1; i <= amount; i++) {
    for (const c of coins) {
      if (c <= i && dp[i - c] !== Infinity) {
        dp[i] = Math.min(dp[i], dp[i - c] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Tradeoff: Bottom-up DP. The Infinity sentinel marks unreachable amounts. Final check converts to -1 per the prompt.

Workday-specific tips

Workday wants you to explicitly say greedy fails before reaching for DP. State a counterexample (coins=[1,3,4], amount=6) so they see you've tested the assumption. dp[0] = 0 is the base case — articulate why.

Common mistakes

  • Greedy without justifying — wrong on adversarial inputs.
  • Forgetting dp[0] = 0.
  • Returning Infinity instead of -1 for unreachable.

Follow-up questions

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

  • Coin Change II (LC 518) — count combinations.
  • Number of Combinations (target sum) — DP with order vs no order.
  • What if coins can be used at most once?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why does greedy fail?

Greedy is optimal only for canonical coin systems (e.g., US currency). Arbitrary sets like [1,3,4] break it: amount 6 -> greedy 4+1+1=3 vs optimal 3+3=2.

Top-down with memo?

Yes, also O(amount * coins). Recursive structure: f(rem) = 1 + min(f(rem - c) for c in coins). Memoize to avoid recomputation.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →