0

The following code attempts to solve the integer break problem using bottom-up DP. Which line contains a subtle bug that can cause incorrect results on some inputs?

medium🐞 Bug Identification Q14 of Q15

Dynamic Programming: Knapsack - Integer Break

The following code attempts to solve the integer break problem using bottom-up DP. Which line contains a subtle bug that can cause incorrect results on some inputs?

def integer_break(n):
    dp = [0] * n
    dp[1] = 1
    for i in range(2, n + 1):
        max_product = 0
        for j in range(1, i):
            max_product = max(max_product, max(j, dp[j]) * max(i - j, dp[i - j]))
        dp[i] = max_product
    return dp[n]

ALine 3: dp[1] = 1 base case initialization

BLine 2: dp array size is n instead of n+1

CLine 5: Outer loop range from 2 to n+1

DLine 7: Using max(j, dp[j]) instead of just dp[j]

Step-by-Step Solution

Step 1: Check dp array size
dp is initialized with size n, but indices up to n are accessed (dp[i], dp[i-j]) which requires size n+1.
Step 2: Consequences of wrong size
Accessing dp[n] or dp[i-j] when i=n causes index out of range or incorrect results.
Final Answer:
Option B -> Option B
Quick Check:
dp array must be size n+1 to safely index up to n [OK]

Quick Trick: Check array size matches max index accessed [OK]

Common Mistakes:

MISTAKES

Forgetting dp size off-by-one
Misplacing base case initialization

Trap Explanation:

PITFALL

The code looks correct except for dp size; this subtle bug often passes small tests but fails on larger inputs.

Interviewer Note:

CONTEXT

Tests attention to detail and understanding of DP array indexing

Master "Integer Break" 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