Bit Manipulation - Find the Missing Number
Given the final XOR result is 5 after processing an array of length 5, which of the following input arrays could have produced this result assuming numbers range from 0 to 5 with one missing?
Given the final XOR result is 5 after processing an array of length 5, which of the following input arrays could have produced this result assuming numbers range from 0 to 5 with one missing?
hard🔄 Reverse Engineer Q9 of Q15
Step-by-Step Solution
Solution:
Step 1: XOR all numbers 0 to 5
0^1^2^3^4^5 = 1 (since XOR of 0..5 is 1)Step 2: XOR input array elements
For [0,2,3,4,5]: 0^2=2, 2^3=1, 1^4=5, 5^5=0Step 3: XOR final result
XOR_all ^ XOR_array = 1 ^ 0 = 1, which does not match 5, so check other options.Step 4: Check [0,1,2,3,4]
For [0,1,2,3,4]: XOR_array = 0^1=1, 1^2=3, 3^3=0, 0^4=4; XOR_all ^ XOR_array = 1 ^ 4 = 5 matches final XOR result.Final Answer:
Option D -> Option DQuick Check:
[0,1,2,3,4] missing number is 5, matches XOR result 5 [OK]
Quick Trick: XOR_all ^ XOR_array = missing number [OK]
Common Mistakes:
MISTAKES- Not XORing full range
- Miscomputing XOR of array elements
Trap Explanation:
PITFALL- Candidates often confuse XOR of full range and array, leading to wrong input guess.
Interviewer Note:
CONTEXT- Tests deep understanding of XOR properties and reverse reasoning.
Master "Find the Missing Number" in Bit Manipulation
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Bit Manipulation Quizzes