125. Single Number II

Track two bit-masks, ones and twos, that record which bits have been seen once and twice (mod 3). Each number updates them so that any bit reaching a third occurrence resets to zero. After the pass, ones holds the unique number's bits.

Idea

Every bit position, across the whole array, is set a multiple of 3 times — plus whatever the unique number contributes. So if we count each bit's occurrences mod 3, the leftover is exactly the unique number's bits.

Rather than 32 separate counters, two integers ones and twos act as bitwise mod-3 counters in parallel. The update keeps each bit's state cycling 0 → ones → twos → 0:

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

A bit that appears a third time is cleared from both. After processing everything, ones holds the answer.

Algorithm

1. ones = twos = 0.
2. For each num: apply the two updates above.
3. Return ones.

Worked example: [2,2,3,2]

The three 2s cycle their bits back to zero; only 3's bits remain in ones → 3.

Complexity

• Time: O(n).
• Space: O(1) — two integers, satisfying the constant-space requirement.

class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for (int num : nums) {
            ones = (ones ^ num) & ~twos;
            twos = (twos ^ num) & ~ones;
        }
        return ones;
    }
}