Given a non-empty array of integers nums where every element appears exactly twice except for one, find that single element — in linear time, without extra space beyond a constant.
Example
Input nums = [4,1,2,1,2]
Output 4
Key Pointers
XOR is its own inverse: a ^ a = 0 and a ^ 0 = a.
XOR is commutative and associative, so the order the numbers arrive in doesn't matter.
XOR every number together — every pair cancels itself out to 0, leaving only the number with no partner.
Step-by-Step Analysis
Initialize result = 0.
For each number n in nums, update result ^= n.
Every value that appears twice XORs itself away by the end.
Return result — the one value left unpaired.
Complexity
Time: O(n) — Space: O(1)
Code
def singleNumber(nums: list[int]) -> int:
result = 0
for n in nums:
result ^= n
return result
Code Explanation
How the solution above works, piece by piece.
XOR has two useful rules: x ^ x = 0 and x ^ 0 = x. It's also order-independent.
XOR-ing every number means each pair cancels out, whatever order they appear in.
What remains is the number without a partner.
O(n) time and O(1) space; no hash set needed.
Visual Walkthrough
Running it on nums = [4, 1, 2, 1, 2]:
The result is shown in binary after each XOR. The two 1s cancel, the two 2s cancel, and 4 (100) is left.