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).