0

Consider the following Python function to find two missing numbers from 1 to n using XOR partitioning. Given n = 4 and arr = [1, 3], what is the final returned list?

easy🧾 Code Trace Q12 of Q15

Bit Manipulation - Find Two Missing Numbers

Consider the following Python function to find two missing numbers from 1 to n using XOR partitioning. Given n = 4 and arr = [1, 3], what is the final returned list?

A[4, 2]

B[1, 3]

C[2, 4]

D[3, 1]

Step-by-Step Solution

Step 1: Compute xor_all
xor_all = 1^2^3^4 ^ 1^3 = (1^1)^(2)^(3^3)^(4) = 2 ^ 4 = 6 (binary 110)
Step 2: Find rightmost set bit and partition
set_bit = 6 & (-6) = 2 (binary 010). Partition numbers by this bit: Group 1 (bit set): numbers with bit 2 set -> 2, 3 Group 2 (bit not set): 1, 4 XOR group 1: 2 ^ 3 ^ (arr nums with bit set: 3) = 2 ^ 3 ^ 3 = 2 XOR group 2: 1 ^ 4 ^ (arr nums with bit not set: 1) = 1 ^ 4 ^ 1 = 4 So missing numbers are [2, 4].
Final Answer:
Option C -> Option C
Quick Check:
Output matches expected missing numbers [OK]

Quick Trick: Trace XOR and partition by rightmost set bit carefully [OK]

Common Mistakes:

MISTAKES

Misinterpret bit masking for partition
Mixing order of XOR operations
Confusing missing numbers with present ones

Trap Explanation:

PITFALL

Misreading which numbers belong to which partition leads to wrong missing numbers.

Interviewer Note:

CONTEXT

Tests candidate's ability to mentally execute bitwise XOR partitioning code.

Master "Find Two Missing Numbers" in Bit Manipulation

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 Bit Manipulation Quizzes