Learning Outcome
After this lesson, you should be able to use XOR cancellation to remove duplicate pairs without extra memory.
Problem Statement
Given an integer array where every element appears twice except one, return the single element.
| Input | Output | Why |
|---|---|---|
nums = [4,1,2,1,2] | 4 | 1 cancels with 1, 2 cancels with 2, and 4 remains. |
Brute Force Approach
Use a frequency map and return the value with count 1. This is clear but uses extra memory.
Optimized Approach
XOR every value. Because x xor x = 0 and x xor 0 = x, duplicate pairs cancel out and the unique value remains.
Exact Pseudocode
answer = 0
for x in nums:
answer = answer xor x
return answerReference Code
class Solution:
def singleNumber(self, nums):
answer = 0
for x in nums:
answer ^= x
return answerSample Dry Run
| Step | State | Result |
|---|---|---|
| Start | answer = 0 | No value processed |
| XOR 4,1,2 | answer changes with each value | Temporary result is not final yet |
| XOR second 1 and 2 | Duplicate pairs cancel | Only 4 remains |
| Return | answer = 4 | single number found |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(n) | Each number is XORed once. |
| Space | O(1) | Only one answer variable is stored. |
Edge Cases
- The trick assumes every non-answer value appears exactly twice.
- Negative numbers still work with XOR.
- Do not use addition as a replacement for XOR cancellation.
Interview Checklist
- Initialize answer to 0.
- XOR every number exactly once.
- State the XOR identities: x xor x = 0 and x xor 0 = x.
FAQs
Why does XOR remove duplicates?
Equal values XOR to zero, and XOR is associative and commutative, so pairs cancel regardless of order.
Why is space O(1)?
No map or set is needed; the running XOR holds the answer.
What is the core pattern?
XOR cancellation.