Single Number
Medium · rating 1100 · Bit Manipulation, Arrays
The first line contains n (odd). The second line contains n integers where every value appears exactly twice except one. Print that single value.
Constraints: 1 ≤ n ≤ 105
Editorial
Approach (XOR trick)
XOR has two useful properties: x ^ x = 0 and x ^ 0 = x. XOR every element together — each value that appears twice cancels to 0, leaving only the element that appears once.
ans = 0
for x in nums:
ans ^= x
return ansWhy it beats a hash set
A hash set also solves it in O(n) time but needs O(n) space; XOR does it in O(1) space with no bookkeeping.
Complexity
Time: O(n). Space: O(1).
Related problems
- Count Set Bits — Medium
- Grade Distribution — Medium
- Majority Element — Medium
- Search Insert Position — Medium
- Sort the Array — Easy
- Account Balance — Easy