Bit Manipulation - Single Number III (Two Singles)
What is the output of the XOR and partition approach when the input array is
[4, 1, 2, 1, 2, 5]?What is the output of the XOR and partition approach when the input array is [4, 1, 2, 1, 2, 5]?
easy🧾 Trace Q3 of Q15
Step-by-Step Solution
Solution:
Step 1: XOR all elements
4 ^ 1 ^ 2 ^ 1 ^ 2 ^ 5 = 4 ^ 5 = 1 (intermediate XOR is 1)Step 2: Find rightmost set bit in XOR result
Set bit mask = 1 (binary 0001)Step 3: Partition elements by this bit and XOR each group
Group 1 (bit set): 1,1,5 -> XOR = 5
Group 2 (bit not set): 4,2,2 -> XOR = 4Final Answer:
Option A -> Option AQuick Check:
Partitioning isolates unique numbers correctly [OK]
Quick Trick: XOR all, partition by set bit, XOR groups [OK]
Common Mistakes:
MISTAKES- Misidentifying the set bit mask
- Incorrect partitioning of elements
- Assuming order of output matters
Trap Explanation:
PITFALL- Confusing which elements belong to which partition leads to wrong output.
Interviewer Note:
CONTEXT- Tests ability to trace XOR and partition logic on sample input.
Master "Single Number III (Two Singles)" in Bit Manipulation
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Bit Manipulation Quizzes