0

The following code attempts to compute the minimum number of perfect squares summing to n. Which line contains a subtle bug that can cause incorrect results or infinite loops?

medium🐞 Bug Identification Q14 of Q15

Dynamic Programming: Knapsack - Perfect Squares

The following code attempts to compute the minimum number of perfect squares summing to n. Which line contains a subtle bug that can cause incorrect results or infinite loops?

ALine 3: Missing base case assignment dp[0] = 0

BLine 2: dp initialization with infinity

CLine 5: Outer loop from 1 to n

DLine 7: Inner loop condition j*j <= i

Step-by-Step Solution

Solution:

Step 1: Identify base case importance
dp[0] = 0 is critical because it represents zero squares needed to sum to zero. Without it, dp[0] remains infinity, causing dp[i] updates to use invalid values.
Step 2: Analyze impact of missing dp[0] = 0
Since dp[0] is infinity, expressions like 1 + dp[i - j*j] become infinity, preventing dp[i] from ever updating correctly, leading to infinite loops or wrong results.
Final Answer:
Option A -> Option A
Quick Check:
Missing dp[0] base case breaks DP initialization [OK]

Quick Trick: dp[0] must be zero to start DP correctly [OK]

Common Mistakes:

MISTAKES

Forgetting dp[0] initialization
Misplacing loop boundaries

Trap Explanation:

PITFALL

Commenting out dp[0] = 0 looks harmless but breaks all dp updates silently.

Interviewer Note:

CONTEXT

Tests if candidate knows critical DP base cases and their effect on correctness.

Master "Perfect Squares" in Dynamic Programming: Knapsack

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions

More Dynamic Programming: Knapsack Quizzes