0

Given the following code snippet implementing the optimal solution for the Ones and Zeroes problem, what is the output for strs = ["10", "0"], m = 1, n = 1?

easy🧾 Code Trace Q3 of Q15

Dynamic Programming: Knapsack - Ones and Zeroes (2D Knapsack)

Given the following code snippet implementing the optimal solution for the Ones and Zeroes problem, what is the output for strs = ["10", "0"], m = 1, n = 1?

A3

B2

C0

D1

Step-by-Step Solution

Solution:

Step 1: Count zeros and ones for each string
"10" has 1 zero, 1 one; "0" has 1 zero, 0 ones.
Step 2: Update dp table backwards
Both strings fit within m=1 zeros and n=1 ones, so dp[1][1] = 2.
Final Answer:
Option B -> Option B
Quick Check:
Both strings fit constraints -> max count 2 [OK]

Quick Trick: Count zeros/ones, update dp backwards [OK]

Common Mistakes:

MISTAKES

Forgetting to update dp backwards
Miscounting zeros or ones

Trap Explanation:

PITFALL

Candidates often miss that both strings fit and only count one.

Interviewer Note:

CONTEXT

Tests ability to trace DP updates on simple input.

Master "Ones and Zeroes (2D Knapsack)" 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