Single Number II: Bit Counting Modulo 3

Every element in an integer array appears exactly three times, except for one element that appears exactly once. Find that single element. You must do it in O(n) time and O(1) space.

This is LeetCode 137: Single Number II. If you have seen Single Number (LeetCode 136), where every element appears twice, you know that XOR solves it in one pass because XOR cancels pairs. But XOR does not cancel triples. You need a different technique entirely.

Examples:

• [2, 2, 3, 2] returns 3
• [0, 1, 0, 1, 0, 1, 99] returns 99

The core insight: bit counting modulo 3

Forget the numbers themselves. Think about individual bit positions across all the numbers.

If a number appears three times, each of its set bits contributes exactly 3 to the count at that position. Three is divisible by three, so those contributions vanish when you take the count modulo 3. The only bits left after the modulo operation belong to the number that appeared once.

This is the key: count the number of 1-bits at each position, take each count modulo 3, and the remainders form the binary representation of the single number.

Approach 1: Bit counting with a loop

The most direct approach is to iterate over all 32 bit positions. For each position, count how many numbers have a 1 at that position. If the count is not divisible by 3, the single number has a 1 at that position.

def single_number(nums):
    result = 0
    for i in range(32):
        bit_sum = 0
        for num in nums:
            if num & (1 << i):
                bit_sum += 1
        if bit_sum % 3:
            result |= 1 << i
    if result >= 2**31:
        result -= 2**32
    return result

This runs in O(32n) = O(n) time and O(1) space. It checks each of the 32 bit positions, and for each position it scans the entire array. The final adjustment handles negative numbers in languages with two's complement representation.

Approach 2: The ones/twos state machine

The bit counting loop works, but you can do it in a single pass by maintaining two variables: ones and twos. These track which bits have appeared once and which have appeared twice (modulo 3).

The idea is a state machine for each bit position. Each bit cycles through three states:

• State 0: the bit has appeared 0 times (mod 3). Both ones and twos have 0 at this position.
• State 1: the bit has appeared 1 time (mod 3). ones has 1, twos has 0.
• State 2: the bit has appeared 2 times (mod 3). ones has 0, twos has 1.
• When the count hits 3, the state resets to 0.

The update rules per element x:

1. ones = (ones ^ x) & ~twos -- XOR flips the bit, but only keep it if twos does not already have it.
2. twos = (twos ^ x) & ~ones -- same logic, but for the second occurrence.

def single_number(nums):
    ones = 0
    twos = 0
    for x in nums:
        ones = (ones ^ x) & ~twos
        twos = (twos ^ x) & ~ones
    return ones

After processing every element, ones holds exactly the bits that appeared a number of times congruent to 1 modulo 3. Since the single number appeared once and every other number appeared three times (which is 0 mod 3), ones is the answer.

Step-by-step walkthrough

Let's trace the state machine approach through [2, 2, 3, 2]. Watch how ones and twos track the bit counts and how 2's bits reset to zero after the third occurrence.

After processing all four elements, ones = 3 and twos = 0. The single number is 3.

Notice the pattern: when a number appears for the first time, its bits enter ones. On the second occurrence, those bits move from ones to twos. On the third occurrence, both ones and twos clear those bits. This three-state cycle is what makes the modulo-3 counting work in constant space.

Complexity analysis

Both approaches satisfy the O(n) time and O(1) space requirements. The state machine approach has a smaller constant factor since it processes all 32 bits simultaneously in a single pass instead of looping over each bit position separately.

Building blocks

This problem decomposes into two reusable building blocks that CodeBricks drills independently:

Bitwise counting

The ability to count how many numbers have a set bit at a given position and use modulo arithmetic to filter out contributions from elements that appear a certain number of times. This technique generalizes beyond triples. Any time you need to isolate bits that do not appear in a specific multiple, per-position counting modulo that multiple does the job.

bit_sum = sum(1 for num in nums if num & (1 << i))
if bit_sum % 3:
    result |= 1 << i

State machine bit manipulation

Using multiple bitmask variables (ones, twos) to simulate a finite state machine that cycles through states as bits accumulate. The XOR-and-mask pattern (var ^ x) & ~other is the core operation: XOR toggles the incoming bit, and the mask prevents it from being set if the other variable already tracks it.

ones = (ones ^ x) & ~twos
twos = (twos ^ x) & ~ones

This pattern is worth drilling until the update rules feel automatic. You should be able to write both lines from memory and explain why the mask (& ~twos and & ~ones) prevents a bit from appearing in both variables simultaneously.

Edge cases

Single element array: If nums contains just one element, that element is the answer. Both approaches handle this correctly. The bit counting approach finds the element's bits with counts of 1 (which is not divisible by 3). The state machine sets ones to that element after one iteration.

Negative numbers: The bit counting approach needs a sign correction for languages that use two's complement. If the 31st bit is set after counting, the result must be adjusted by subtracting 2^32. Python's arbitrary-precision integers require this manual step. The state machine approach handles negatives naturally because the XOR and AND operations work on all bits uniformly.

Zero as the single number: If the unique element is 0, every bit position has a count divisible by 3 (since only the triple-occurring numbers contribute). The result is 0. Both approaches return 0 correctly because no bit position triggers the "not divisible by 3" condition.

From understanding to recall

Understanding the ones/twos state machine in one reading is achievable. Reconstructing the exact update formulas under interview pressure is a different challenge. The lines ones = (ones ^ x) & ~twos and twos = (twos ^ x) & ~ones are compact but easy to mix up if you have not internalized them.

Spaced repetition closes that gap. You type the state machine from scratch today, then again in a few days, then again after a longer interval. Each time, the retrieval gets faster and the formula becomes part of your working vocabulary. When you encounter a variant (like Single Number III, where two numbers appear once), the bitwise reasoning is already automatic and you can focus on the new twist instead of rederiving the fundamentals.

Related posts

• XOR Cancellation Pattern - The simpler version of this problem where elements appear twice. XOR cancels pairs directly, but does not cancel triples. Understanding the XOR approach first makes the modulo-3 extension here feel like a natural next step.
• Number of 1 Bits - Another bit manipulation fundamental. Counting set bits and clearing the lowest set bit with n & (n-1) are the building blocks that make per-position bit analysis intuitive.