137. Single Number II

Time: O(n)

Space: O(1)

Intuition

Every number appears three times except one which appears once. Use two bit-accumulator variables `ones` and `twos` that track bits seen 1 and 2 times mod 3. The state machine transitions ensure bits seen 3 times are zeroed out.

Algorithm

1ones = 0, twos = 0.
2For each num: ones = (ones ^ num) & ~twos. twos = (twos ^ num) & ~ones.
3Return ones (contains bits seen exactly once).

Example Walkthrough

Input: [2,2,3,2]

1.After 2: ones=2, twos=0. After 2: ones=0, twos=2. After 3: ones=3, twos=2. After 2: ones=3, twos=0.

Output: 3

Common Pitfalls

•The order of updating ones and twos matters - compute new ones first, then new twos using the updated ones.

137.cs

// Approach: Bit circuit with ones/twos variables — each bit accumulates modulo 3
// so it clears from both after appearing three times.
// Time: O(n) Space: O(1)

public class Solution
{
    public int SingleNumber(int[] nums)
    {
        int ones = 0, twos = 0;

        for (int i = 0; i < nums.Length; i++)
        {
            ones ^= nums[i] & ~twos;
            twos ^= nums[i] & ~ones;
        }

        return ones;
    }
}

Was this solution helpful?