Given a non-empty integer array nums in which every value appears exactly twice except one value that appears once, return that single value. Your solution should run in linear time and use only constant extra space.
- 1 <= nums.length <= 3 * 10^4
- -3 * 10^4 <= nums[i] <= 3 * 10^4
- Every element appears twice except for one
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Counting with a hash map or sorting the array works, but costs O(n) space or O(n log n) time. XOR gives a neat trick: x ^ x = 0, x ^ 0 = x, and XOR is commutative and associative, so the order of the numbers does not matter. If we XOR every element, each pair cancels to 0 and only the single number is left. This also works for negative numbers because XOR acts on the bit pattern.
Algorithm
- Set
res = 0. - For each
xinnums, dores ^= x. - Return
res.
O(n)Space: O(1)class Solution: def singleNumber(self, nums: List[int]) -> int: res = 0 for x in nums: res ^= x # pairs cancel: x ^ x = 0 return res