Bird
Raised Fist0

Given the following code for lastStoneWeightII, what is the returned value when stones = [1, 2, 3]?

easy🧾 Code Trace Q12 of Q15
Dynamic Programming: Knapsack - Last Stone Weight II
Given the following code for lastStoneWeightII, what is the returned value when stones = [1, 2, 3]?
A1
B0
C2
D3
Step-by-Step Solution
  1. Step 1: Calculate total and half

    Total = 6, half = 3. dp array size = 4, dp[0] = true initially.
  2. Step 2: Update dp for each stone

    For weight=1: dp[1]=true; for weight=2: dp[3]=true (since dp[1] was true), dp[2]=true; for weight=3: dp[3]=true remains.
  3. Step 3: Find largest w ≤ half with dp[w] = true

    dp[3] is true, so minimal difference = total - 2*3 = 6 - 6 = 0.
  4. Final Answer:

    Option B -> Option B
  5. Quick Check:

    Subset {1,2,3} sums to 6; partition into {3} and {1,2} sums 3 and 3 -> difference 0 [OK]
Quick Trick: Check dp array for sums up to half total [OK]
Common Mistakes:
MISTAKES
  • Returning total instead of minimal difference
  • Off-by-one error in dp indexing
  • Not iterating backwards in dp update
Trap Explanation:
PITFALL
  • Candidates often confuse dp indexing or final sum calculation, leading to off-by-one or wrong difference.
Interviewer Note:
CONTEXT
  • Tests ability to trace DP updates and final result calculation.
Master "Last Stone Weight II" 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