Single Number II
Problem
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.
nums = [2,2,3,2]3ones and twos. For each bit position, count how many times it appears mod 3 across all numbers. The classic update keeps ones = bits seen 1 mod 3 times.def single_number(nums):
ones = twos = 0
for x in nums:
ones = (ones ^ x) & ~twos
twos = (twos ^ x) & ~ones
return onesfunction singleNumber(nums) {
let ones = 0, twos = 0;
for (const x of nums) {
ones = (ones ^ x) & ~twos;
twos = (twos ^ x) & ~ones;
}
return ones;
}class Solution {
public int singleNumber(int[] nums) {
int ones = 0, twos = 0;
for (int x : nums) {
ones = (ones ^ x) & ~twos;
twos = (twos ^ x) & ~ones;
}
return ones;
}
}int singleNumber(vector<int>& nums) {
int ones = 0, twos = 0;
for (int x : nums) {
ones = (ones ^ x) & ~twos;
twos = (twos ^ x) & ~ones;
}
return ones;
}Explanation
Every value appears three times except one lone value. Plain XOR (which solves the "appears twice" version) does not work here, because three copies of a number XOR down to the number itself, not to zero.
The fix is to track each bit position modulo 3 using two bitmasks, ones and twos. Think of them as a tiny counter per bit: ones holds bits that have been seen 1 time (mod 3), and twos holds bits seen 2 times (mod 3). When a bit reaches the third sighting, both masks clear it back to zero.
The updates ones = (ones ^ x) & ~twos and then twos = (twos ^ x) & ~ones implement exactly that mod-3 counting. The & ~twos and & ~ones parts are what reset a bit once it has been counted three times.
After processing the whole array, every bit belonging to a thrice-repeated value has cycled back to zero, so ones holds only the bits of the value that appeared once.
Example: nums = [2,2,3,2]. The three 2s cancel out across the mod-3 counting, leaving ones = 3, the lone value.