Single Number II — 3-State Bit Counting
Sanjeev SharmaAdvertisement
Problem
Every element appears 3 times except one. Find the single one.
Approach 1 — Bit Count Mod 3
For each bit position, count total set bits. If count mod 3 != 0, the single number has that bit set.
Approach 2 — Two Bitmask State Machine
ones = bits seen once, twos = bits seen twice. Update:
ones = (ones ^ n) & ~twostwos = (twos ^ n) & ~ones
Time: O(n) | Space: O(1)
Solutions
Python — Bit Count
class Solution:
def singleNumber(self, nums: list[int]) -> int:
ans=0
for bit in range(32):
total=sum((n>>bit)&1 for n in nums)
if total%3:
if bit==31: ans-=(1<<31)
else: ans|=(1<<bit)
return ans
Python — Two bitmasks
class Solution:
def singleNumber(self, nums: list[int]) -> int:
ones=twos=0
for n in nums:
ones=(ones^n)&~twos
twos=(twos^n)&~ones
return ones
C++
class Solution {
public:
int singleNumber(vector<int>& nums){
int ones=0,twos=0;
for(int n:nums){ones=(ones^n)&~twos;twos=(twos^n)&~ones;}
return ones;
}
};
Complexity
- Time: O(n) | Space: O(1)
Advertisement
