Exact Change

TIP103 Unit 11 Session 1 (Click for link to problem statements)

Exact Change

A vending machine can dispense coins of the denominations in coins and needs to make exactly amount in change using as few coins as possible. Coins may be reused any number of times.

Return the minimum number of coins that sum to amount, or -1 if it cannot be made.

def coin_change(coins, amount):
    pass

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 25-35 mins
• 🛠️ Topics: Dynamic Programming, Bottom-Up Tabulation, Unbounded Knapsack

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: Can the same coin denomination be used more than once?

  • A: Yes, coins may be reused any number of times, so amount = 10 can be made with two 5 coins.

• Q: What should the function return if the amount cannot be made exactly?

  • A: Return -1. For example, with coins = [2] there is no way to make an odd amount like 3.

• Q: What should the function return if amount is 0?

  • A: Return 0. No coins are needed to make zero change.

HAPPY CASE
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 can be made as 5 + 5 + 1, which uses 3 coins. No combination uses fewer.

EDGE CASE
Input: coins = [2], amount = 3
Output: -1
Explanation: Every combination of 2s is even, so an amount of 3 can never be made exactly.

Input: coins = [1, 3, 4], amount = 6
Output: 2
Explanation: The best answer is 3 + 3. A greedy approach that always takes the largest coin first would pick 4 + 1 + 1 and incorrectly use 3 coins.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Optimization Problems with Overlapping Subproblems, we can consider the following approaches:

• Dynamic Programming (Bottom-Up Tabulation): The minimum coins for amount depends on the minimum coins for smaller amounts (amount - coin). This optimal substructure plus heavily overlapping subproblems is the classic DP signature. Because each coin can be reused, this is the unbounded knapsack pattern.
• Greedy (does NOT work): Always taking the largest coin fails for denominations like [1, 3, 4] with amount = 6, so we cannot shortcut the DP.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Build a table dp where dp[a] is the minimum number of coins needed to make amount a. Zero change needs zero coins, so dp[0] = 0. For every larger amount, try ending the combination with each coin: if we use coin, we need dp[a - coin] + 1 coins in total. Take the best choice over all coins. Amounts that stay at infinity are unreachable.

1) Create a dp array of size amount + 1.
   a) dp[0] = 0 (zero coins make zero change).
   b) Every other entry starts at infinity (not yet reachable).
2) For each amount a from 1 to amount:
   a) For each coin in coins:
      i) If coin <= a and dp[a - coin] + 1 < dp[a], update dp[a] = dp[a - coin] + 1.
3) If dp[amount] is still infinity, return -1.
4) Otherwise return dp[amount].

⚠️ Common Mistakes

• Trying a greedy largest-coin-first strategy, which gives wrong answers for denominations like [1, 3, 4].
• Initializing dp[0] to infinity instead of 0, which makes every amount unreachable.
• Forgetting to skip coins larger than the current amount, causing a negative index into dp.
• Returning infinity (or crashing) instead of -1 when the amount cannot be made.

4: I-mplement

Implement the code to solve the algorithm.

def coin_change(coins, amount):
    # dp[a] = minimum number of coins needed to make amount a
    # Amount 0 needs 0 coins; everything else starts as unreachable
    dp = [0] + [float('inf')] * amount

    # Build up the answer for every amount from 1 to the target
    for a in range(1, amount + 1):
        for coin in coins:
            # If we can end a combination for amount a with this coin,
            # it costs one more coin than the best answer for a - coin
            if coin <= a and dp[a - coin] + 1 < dp[a]:
                dp[a] = dp[a - coin] + 1

    # If the target is still unreachable, exact change cannot be made
    return dp[amount] if dp[amount] != float('inf') else -1

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: coins = [1, 2, 5], amount = 11

  • dp starts as [0, inf, inf, ..., inf].
  • Small amounts fill in first: dp[1] = 1, dp[2] = 1, dp[3] = 2, dp[4] = 2, dp[5] = 1.
  • Building further: dp[6] = 2 (5+1), dp[7] = 2 (5+2), dp[10] = 2 (5+5).
  • Finally dp[11] = dp[10] + 1 = 3, using coins 5 + 5 + 1.
  • Output: 3

• Input: coins = [2], amount = 3

  • dp[1] never updates (the only coin, 2, is too big), so dp[1] = inf.
  • dp[2] = 1, but dp[3] = dp[1] + 1 = inf — amount 3 is unreachable.
  • dp[3] is still infinity, so the function returns -1.
  • Output: -1

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume A is the target amount and C is the number of coin denominations in coins.

• Time Complexity: O(A * C) because we compute an answer for every amount from 1 to A, and each computation tries all C coins.
• Space Complexity: O(A) for the dp table with one entry per amount from 0 to A.