Single Number
The key idea
XOR has two magic properties:
x ^ x = 0 (a number cancels itself) and x ^ 0 = x (XOR with zero is a no-op). Fold XOR across the whole array and every paired element cancels out, leaving only the element that appears once.Problem
Given a non-empty array of integers nums, every element appears twice except for one. Find that single element.
You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.
Constraints
1 <= nums.length <= 3 * 10^4-3 * 10^4 <= nums[i] <= 3 * 10^4- Each element appears twice except for one element which appears once.
Examples
Input: nums = [2,2,1]
Output: 1
Input: nums = [4,1,2,1,2]
Output: 4
Input: nums = [1]
Output: 1
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization