Coding Interview PatternsSingle Number II
MediumBitwise Manipulation
Single Number II
Explanation & Solution
Description
Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.
You must implement a solution with linear runtime complexity and use only constant extra space.
Input:nums = [2,2,3,2]
0
2
1
2
2
3
3
2
Output: 3
Constraints
1 <= nums.length <= 3 * 10^4-2^31 <= nums[i] <= 2^31 - 1- Each element appears exactly three times except for one element which appears once.
Approach
Bitwise Manipulation pattern
Key Insight
- After processing all numbers,
onescontains the bit pattern of the element that appeared exactly once (1 mod 3 = 1) - Time: O(n) | Space: O(1)
Visualization
Input:
[2, 2, 3, 2]
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps