Find the XOR of Numbers Which Appear Twice

Find the XOR of Numbers Which Appear Twice

1. What is this problem about?

The Find the XOR of Numbers Which Appear Twice interview question is a bitwise and frequency-based challenge. You are given an array of integers where some numbers appear once and some appear exactly twice. Your goal is to find all numbers that appear twice and calculate their bitwise XOR sum.

2. Why is this asked in interviews?

Companies like Meta and Google ask the Find the XOR of Numbers coding problem to test a candidate's ability to use Bit Manipulation interview patterns efficiently. While you can solve it with a frequency map, the XOR operator is often requested as an optimization or as part of a trick to handle specific bitwise constraints. It evaluations your understanding of how XOR can be used to "cancel out" or "isolate" values in a set.

3. Algorithmic pattern used

This problem combines the Hash Table and Bit Manipulation patterns.

1. Identify Duplicates: Use a frequency map or a boolean array (if the range of numbers is small) to track which numbers have been seen.
2. Calculate XOR: Maintain a running variable xorSum initialized to 0.
3. Iteration: As you traverse the array:
   • If a number has already been seen (making it its second appearance), XOR it into the xorSum.
4. Result: The final value of xorSum is the XOR sum of all numbers that appeared exactly twice.

4. Example explanation

Array: [1, 2, 1, 3, 2]

1. Read 1: First time. Mark 1 as seen.
2. Read 2: First time. Mark 2 as seen.
3. Read 1: Already seen! xorSum = 0 ^ 1 = 1.
4. Read 3: First time. Mark 3 as seen.
5. Read 2: Already seen! xorSum = 1 ^ 2 = 3. Result: 3.

5. Common mistakes candidates make

• XORing everything: Forgetting that XORing every number in the array once won't isolate the duplicates correctly (it would actually cancel out the duplicates and leave the XOR sum of numbers that appeared once).
• Incorrect Initialization: Starting xorSum with a value other than 0.
• Double Counting: XORing a number three times if it appears more than twice (though usually the constraints specify exactly once or twice).

6. Interview preparation tip

Always remember the property $X \oplus X = 0$. In problems where you need to find elements that appear an odd or even number of times, XOR is usually the most efficient $O(1)$ space tool available.