# 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](https://leetcode.com/problems/single-number-ii/?utm_source=chatgpt.com))

## Examples

Example 1:

```python
nums = [2, 2, 3, 2]
```

The number `2` appears three times.

The number `3` appears once.

Output:

```python
3
```

Example 2:

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

The numbers `0` and `1` appear three times.

The number `99` appears once.

Output:

```python
99
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | `nums: list[int]` |
| Output | The integer appearing once |
| Rule | Every other integer appears exactly three times |
| Required time | `O(n)` |
| Required space | `O(1)` |

Function shape:

```python
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:

```python
x ^ x = 0
```

But here numbers appear three times:

```text
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:

```text
0 + 0 + 0 = 0
```

or:

```text
1 + 1 + 1 = 3
```

Both are divisible by `3`.

Only the single number contributes a remainder.

So for every bit position:

```python
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:

```python
nums = [2, 2, 3, 2]
```

Binary:

| Number | Binary |
|---:|---|
| `2` | `0010` |
| `2` | `0010` |
| `3` | `0011` |
| `2` | `0010` |

Count each bit:

| Bit position | Sum | Sum % 3 |
|---:|---:|---:|
| `0` | `1` | `1` |
| `1` | `4` | `1` |
| `2` | `0` | `0` |
| `3` | `0` | `0` |

Reconstructed binary:

```text
0011
```

which equals:

```python
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:

```python
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:

```text
11111111111111111111111111111111
```

represents:

```python
-1
```

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

## Algorithm

Initialize:

```python
answer = 0
```

For each bit position from `0` to `31`:

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

```python
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:

```python
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.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(32 * n)` | Scan all numbers for each bit |
| Space | `O(1)` | Only integer variables are used |

Since `32` is constant, the time complexity simplifies to:

```python
O(n)
```

## Implementation

```python
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:

```python
for bit in range(32):
```

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

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

This extracts the bit using right shift and bit masking.

If the remainder modulo `3` is nonzero:

```python
if count % 3:
```

then the unique number must contain that bit.

So we set it:

```python
answer |= (1 << bit)
```

After reconstructing all 32 bits, we handle negative numbers:

```python
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:

| Variable | Meaning |
|---|---|
| `ones` | Bits seen once |
| `twos` | Bits seen twice |

Transitions happen automatically through bitwise logic.

Implementation:

```python
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

```python
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:

| Test | Why |
|---|---|
| `[2, 2, 3, 2]` | Standard example |
| `[0, 1, 0, 1, 0, 1, 99]` | Multiple repeating numbers |
| Negative unique value | Sign handling |
| Single-element array | Minimum size |
| Unique zero | Zero bit pattern |
| Repeated negative values | Negative duplicates |