Coding Interview PatternsSingle Number
EasyBitwise Manipulation
Single Number
Explanation & Solution
Description
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with linear runtime complexity and use only constant extra space.
Input:nums = [2,2,1]
0
2
1
2
2
1
Output: 1
Constraints
1 <= nums.length <= 3 * 10^4-3 * 10^4 <= nums[i] <= 3 * 10^4- Each element appears exactly twice except for one element which appears once.
Approach
Bitwise Manipulation pattern
Key Insight: XOR Properties
a ^ a = 0— any number XORed with itself is 0a ^ 0 = a— any number XORed with 0 is itself- XOR is commutative and associative
Algorithm
1. Initialize result = 0
2. XOR every number in the array with result
3. All pairs cancel out (x ^ x = 0), leaving only the single number
Key Insight
- Since every element except one appears exactly twice, XORing all elements together causes duplicates to cancel:
2^2^4^1^1 = 0^4^0 = 4 - Time: O(n) | Space: O(1)
Visualization
Input:
[2, 2, 1]
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps