Single Number II
Medium Bit counting
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Every number appears three times except one, which appears once. Find it with O(1) extra space.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: every number appears three times except one.
Why this works: look at one bit position at a time. The triplets add a multiple of 3 to that bit's count, so count % 3 is the single number's bit.
Example: [2, 2, 3, 2] → binary 10, 10, 11, 10
bit 0: 0+0+1+0 = 1 → 1 % 3 = 1bit 1: 1+1+1+1 = 4 → 4 % 3 = 1answer 11 = 3
✦Hints open one at a time
↗Approach
For each of the 32 bit positions, sum the bits across all numbers and take the total mod 3. The remainder is the single number's bit. Rebuild the answer from those bits. Works for negatives too because we handle bit 31 like any other.
</>Solution (Java)
class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for (int bit = 0; bit < 32; bit++) {
int count = 0;
for (int x : nums) count += (x >> bit) & 1;
if (count % 3 != 0) result |= (1 << bit); // the single number owns this bit
}
return result;
}
}!Common mistake
Using a HashMap of counts — correct but O(n) space.
- Time: O(32·n) = O(n).
- Space: O(1).
