Find the Single Among Triples
Problem
Every value in nums appears exactly three times, except for one value that appears once. Return the unique value using O(n) time and O(1) extra space.
Input
nums = [2,2,3,2]Output
3Use two bitmasks
ones 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;
}