Single Number II
The key idea
If every number except one appears exactly three times, then for each bit position the number of
1s contributed by the triples is a multiple of 3. So the count of 1s in any bit position, taken modulo 3, is exactly the bit of the unique number. Summing those surviving bits rebuilds the answer.Problem
Given an integer array nums where every element appears three times except for one element which appears exactly once, return the single element that appears only once.
You must implement a solution with linear runtime complexity and use only constant extra space.
Constraints
1 <= nums.length <= 3 * 10^4-2^31 <= nums[i] <= 2^31 - 1- Each element in
numsappears exactly three times except for one element which appears once.
Examples
Input: nums = [2,2,3,2]
Output: 3
Input: nums = [0,1,0,1,0,1,99]
Output: 99
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