Single Number II — 3-State Bit Counting Every Senior Engineer Knows

Problem Statement#

Given an integer array nums where every element appears exactly three times except for one element which appears exactly once. Find the single element and return it. 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 appears exactly three times except for one element which appears exactly once.

Input:  nums = [2, 2, 3, 2]
Output: 3
Explanation: 2 appears three times. 3 appears once.

Input:  nums = [0, 1, 0, 1, 0, 1, 99]
Output: 99
Explanation: 0 and 1 each appear three times. 99 appears once.

Why This Problem Matters#

Single Number II is one of the most instructive bit-manipulation problems in any interview bank because it forces you to generalize beyond a ^ a = 0. Simple XOR cancels pairs. Triplets do not cancel (a ^ a ^ a = a), so you need a fundamentally different approach. This is exactly the "what if the constraint changes slightly" follow-up that senior engineers receive after solving Single Number.

The problem teaches two powerful ideas. First: bit-position analysis — think about each of the 32 bit positions independently, count how many numbers have that bit set, and apply modular arithmetic. Second: the ones/twos state machine — a pure boolean circuit that tracks which bits have been seen 1 mod 3 times and which have been seen 2 mod 3 times, without ever explicitly counting.

The Core Insight#

Approach 1 — Bit count modulo 3:

For each of the 32 bit positions, count how many numbers have that bit set. Triplicates contribute 3 (a multiple of 3) — they leave no remainder. Only the single element contributes 1. So: if count % 3 != 0, the single element has that bit set.

Approach 2 — Two-bitmask state machine:

Model a 3-state counter per bit using two bitmasks ones and twos:

• ones holds bits seen 1 time mod 3
• twos holds bits seen 2 times mod 3
• When a bit is seen a third time it rolls back to zero (disappears from both masks)

Update rules:

• ones = (ones ^ n) & ~twos
• twos = (twos ^ n) & ~ones

After processing all elements, ones contains exactly the bits of the single element.

Visual Dry Run#

Input: nums = [2, 2, 3, 2] — binary: 2 = 010, 3 = 011

Ones/Twos state machine trace:

Result: ones = 011 = 3. Correct.

Bit count mod 3 verification:

Reconstruct: bit1=1, bit0=1 → 011 = 3. Correct.

Solution (Optimal)#

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        ones, twos = 0, 0
        for n in nums:
            ones = (ones ^ n) & ~twos   # update ones using old twos
            twos = (twos ^ n) & ~ones   # update twos using new ones
        return ones
 
# Alternative: bit count mod 3 (clearer but 32 passes)
class Solution2:
    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)   # handle sign bit for negative numbers
                else:
                    ans |= (1 << bit)
        return ans

var singleNumber = function(nums) {
    let ones = 0, twos = 0;
    for (const n of nums) {
        ones = (ones ^ n) & ~twos;   // update ones using old twos
        twos = (twos ^ n) & ~ones;   // update twos using new ones
    }
    return ones;
};

Time: O(n) — single pass through the array Space: O(1) — only two integer bitmasks

Common Mistakes#

• Applying plain XOR. a ^ a ^ a = a, so XOR of a triplet leaves the element unchanged. Plain XOR gives a wrong answer for this problem.
• Swapping the update order in the state machine. Compute new ones first using old twos, then compute new twos using new ones. Reversing produces incorrect results.
• Forgetting the sign bit in the bit-count approach. In Python, bit 31 is the sign bit for 32-bit integers. Accumulated count at bit 31 needs ans -= (1 << 31) to recover the correct two's complement negative value.
• Confusing this problem with LC 136 (pairs). The XOR-only solution from LC 136 does not apply here.
• Using O(n) space via a hash map. The constraint says O(1) space.

Interview Tips#

• Lead with the bit-count mod 3 approach — it is intuitive and easy to explain.
• Then present the ones/twos state machine as the optimized single-pass version.
• Explicitly say "I update ones first using the old twos, then update twos using the new ones" — this ordering matters and interviewers probe it.
• Mention the generalization: for k appearances you need ceil(log2(k)) bitmasks.

Follow-up Questions#

• What if every element appears k times except one? Generalize. Use k bitmasks tracking counts 0 through k-1 per bit. Alternatively use the bit-count mod k approach, which generalizes directly.
• What if two elements appear once and the rest three times? XOR all to get a^b. Find any set bit. Partition numbers by that bit and apply three-times logic to each group.
• How would you implement this in hardware with minimal gates? The ones/twos formulation is literally a 3-state counter in combinational logic. Each bit position is an independent flip-flop.
• What is the minimum number of bitmasks for k appearances? ceil(log2(k)). For k=3: 2 bitmasks (ones and twos). For k=4: 2 bitmasks (binary counting).

Key Takeaways#

• a ^ a ^ a = a — simple XOR does not cancel triplets; you need modulo-3 arithmetic.
• The bit-count approach works by counting set bits per position and taking count % 3.
• The ones/twos state machine encodes that bit-count logic in just two bitmasks updated per element.
• The update order is critical: compute new ones from old twos, then new twos from new ones.
• For k appearances, you need ceil(log2(k)) bitmasks — XOR (k=2) needs 1, this problem (k=3) needs 2.
• The state machine is directly analogous to a 3-state digital counter circuit.
• This problem is the follow-up interviewers ask immediately after you solve LC 136 Single Number.