Bird
Raised Fist0

Which mistake causes incorrect results when amount = 0?

medium🐛 Buggy Code Q7 of Q15
Dynamic Programming: Knapsack - Coin Change (Minimum Coins)
Examine the following code snippet for minimum coin change. Which mistake causes incorrect results when amount = 0? ```python def minCoins(coins, amount): dp = [0] + [float('inf')] * amount for i in range(1, amount + 1): for coin in coins: if i - coin >= 0: dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] ```
ALooping from 1 to amount excludes amount 0
BInitializing dp[0] to 0 is incorrect
CNo base case for amount 0 leads to infinite loop
DUsing float('inf') causes type errors
Step-by-Step Solution
Solution:
  1. Step 1: Check base initialization

    dp[0] = 0 is correct since zero coins needed for amount 0.
  2. Step 2: Analyze loops

    Loop starts at i=1, so dp[0] is never updated, which is correct.
  3. Step 3: Identify issue

    For amount=0, the function returns dp[0] = 0 immediately, no bug here.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Loop excludes amount 0 but dp[0] is initialized correctly [OK]
Quick Trick: Check loop ranges carefully for base cases [OK]
Common Mistakes:
MISTAKES
  • Misunderstanding dp initialization
  • Assuming dp[0] needs update
  • Confusing loop boundaries
Trap Explanation:
PITFALL
  • Loop boundaries often cause subtle bugs in DP implementations
Interviewer Note:
CONTEXT
  • Tests ability to spot subtle bugs in DP code for coin change
Master "Coin Change (Minimum Coins)" in Dynamic Programming: Knapsack

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Dynamic Programming: Knapsack Quizzes