LeetCode 137: Single Number II

Problem Restatement

We are given an integer array nums.

Every element appears exactly three times except for one element, which appears exactly once.

Return the element that appears once.

The solution must run in linear time and use constant extra space. LeetCode explicitly requires this. (leetcode.com)

Examples

Example 1:

nums = [2, 2, 3, 2]

The number 2 appears three times.

The number 3 appears once.

Output:

3

Example 2:

nums = [0, 1, 0, 1, 0, 1, 99]

The numbers 0 and 1 appear three times.

The number 99 appears once.

Output:

99

Input and Output

Function shape:

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        ...

Why XOR Alone Does Not Work

In LeetCode 136, every duplicate appeared exactly twice.

XOR worked because:

x ^ x = 0

But here numbers appear three times:

x ^ x ^ x = x

The value does not disappear.

So ordinary XOR is insufficient.

We need another idea.

Key Insight: Count Bits

Consider one bit position independently.

Suppose we look only at bit 0.

Every number that appears three times contributes either:

0 + 0 + 0 = 0

or:

1 + 1 + 1 = 3

Both are divisible by 3.

Only the single number contributes a remainder.

So for every bit position:

bit_sum % 3

tells us whether the single number has a 1 at that position.

This reconstructs the answer bit by bit.

Bit-by-Bit Example

Suppose:

nums = [2, 2, 3, 2]

Binary:

Count each bit:

Reconstructed binary:

0011

which equals:

3

Handling Negative Numbers

Python integers do not have fixed width.

LeetCode uses 32-bit signed integers, so we simulate 32 bits.

For bit positions:

0 through 31

we reconstruct the number.

The sign bit is bit 31.

If that bit is set, the result should be interpreted as negative.

For example, in 32-bit signed representation:

11111111111111111111111111111111

represents:

-1

So after reconstructing the bits, if bit 31 is set, convert the result back to a Python negative integer.

Algorithm

Initialize:

answer = 0

For each bit position from 0 to 31:

1. Count how many numbers have that bit set.
2. Compute:

count % 3

3. If the remainder is 1, set that bit in the answer.

Finally, handle the sign bit for negative numbers.

Correctness

Consider any bit position independently.

Every number appearing three times contributes either three zeroes or three ones at that bit position. Therefore, the total contribution from all repeated numbers is divisible by 3.

The only contribution not divisible by 3 comes from the single number.

Thus:

count % 3

equals the bit value of the unique number at that position.

The algorithm reconstructs every bit of the unique number independently, so the final reconstructed integer equals the number that appears once.

If the sign bit is set, the reconstructed 32-bit value represents a negative signed integer, and the conversion step correctly transforms it into Python’s integer representation.

Therefore, the algorithm returns exactly the single number.

Complexity

Let n = len(nums).

We process exactly 32 bit positions.

Since 32 is constant, the time complexity simplifies to:

O(n)

Implementation

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        answer = 0

        for bit in range(32):
            count = 0

            for num in nums:
                if (num >> bit) & 1:
                    count += 1

            if count % 3:
                answer |= (1 << bit)

        if answer >= 2**31:
            answer -= 2**32

        return answer

Code Explanation

We reconstruct the answer bit by bit:

for bit in range(32):

For each bit, count how many numbers contain a 1 there:

if (num >> bit) & 1:
    count += 1

This extracts the bit using right shift and bit masking.

If the remainder modulo 3 is nonzero:

if count % 3:

then the unique number must contain that bit.

So we set it:

answer |= (1 << bit)

After reconstructing all 32 bits, we handle negative numbers:

if answer >= 2**31:
    answer -= 2**32

This converts the unsigned 32-bit representation into a signed Python integer.

Finite-State Bitwise Solution

There is also a more advanced constant-space bitwise state machine solution.

The idea is to track bit counts modulo 3 using two integers:

Transitions happen automatically through bitwise logic.

Implementation:

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        ones = 0
        twos = 0

        for num in nums:
            ones = (ones ^ num) & ~twos
            twos = (twos ^ num) & ~ones

        return ones

This is elegant but much harder to derive during interviews.

The bit-counting approach is usually easier to explain correctly.

Testing

def run_tests():
    s = Solution()

    assert s.singleNumber([2, 2, 3, 2]) == 3
    assert s.singleNumber([0, 1, 0, 1, 0, 1, 99]) == 99
    assert s.singleNumber([-2, -2, -2, -7]) == -7
    assert s.singleNumber([5]) == 5
    assert s.singleNumber([1, 1, 1, 0]) == 0
    assert s.singleNumber([-1, -1, -1, 8]) == 8

    print("all tests passed")

run_tests()

Test meaning: