Single Number II

Subarray Sum Equals K

Search a 2D Matrix

Find the one value that appears a single time when every other value appears exactly three times.

Every value in `nums` appears exactly three times except for one value that appears exactly once. Return the value that appears once.

**Input / output**
- Input: `nums: int[]`
- Output: the unique integer

**Examples**
1. `nums = [2, 2, 3, 2]` returns `3`.
2. `nums = [0, 1, 0, 1, 0, 1, 99]` returns `99`.
3. `nums = [1, 1, 1, 2]` returns `2`.

**Constraints**
- `1 <= nums.length <= 30000`
- `-2^31 <= nums[i] <= 2^31 - 1`
- Every element appears exactly three times except one element that appears once.

**Edge cases**
- Values can be negative.
- The unique value may itself be `0`.

**Target complexity**
- Aim for `O(n)` time and `O(1)` extra space.

**Hints**
1. Count how many times each bit position is set across all numbers.
2. A bit that belongs to the unique number leaves a remainder of `1` when its count is taken modulo `3`.

**Follow-up**
Can you generalize the bit-counting trick for "every element appears `k` times except one"?

- XOR cancels values that appear an even number of times.
- Here duplicates appear three times (odd), so XOR does not cleanly remove them.
- We need to reason bit by bit instead.

Why plain XOR is not enough

- For each of the 32 bit positions, count how many numbers have that bit set.
- Every tripled value contributes a multiple of three, so `count % 3` isolates the unique number's bits.
- Rebuild the answer from the remaining bits (sign-extending the top bit for negatives).

Count each bit modulo three

- Track two masks: `ones` holds bits seen once, `twos` holds bits seen twice.
- A bit resets to zero once it has been seen three times.
- After processing every number, `ones` is exactly the unique value.

Constant-space bitmask automaton

- `ones = (ones ^ num) & ~twos` records bits appearing a first time while clearing any at two.
- `twos = (twos ^ num) & ~ones` promotes bits to the two state, clearing any now back at one.
- This is `O(n)` time and `O(1)` space with no per-bit loop.

Two-mask solution

Trace `nums = [2, 2, 3, 2]` (binary `2 = 10`, `3 = 11`).

| num | ones | twos |
|---:|---:|---:|
| start | `00` | `00` |
| 2 | `10` | `00` |
| 2 | `00` | `10` |
| 3 | `01` | `10` |
| 2 | `01` | `00` |

Final `ones = 01 = 3`, the unique value.

Dry run

The two-mask automaton returns the unique value in `O(n)` time and `O(1)` extra space.