Single Number
Easy· XOR
Problem
Every value in a non-empty array appears exactly twice except for one value that appears once. Find that value using linear time and constant extra space.
Examples
Input: nums = [4,1,2,1,2]
Output: 4
Input: nums = [1]
Output: 1
Constraints
- • 1 <= nums.length <= 3·10^4
- • Every element except one appears twice
Hints & approach
Hint 1
A hash set works but uses O(n) memory.
Hint 2
What is x XOR x? What is x XOR 0?
Hint 3
XOR everything together — pairs cancel out.
Approachtry the hints first
XOR is associative and commutative, x ^ x = 0 and x ^ 0 = x. XOR-ing every element together therefore cancels each duplicated pair, leaving only the lone value. One pass with a single accumulator is all that is needed.
Time O(n) · Space O(1)