Single Number II

Problem Link

Problem Statement

Given an integer array nums where every element appears exactly three times except for one element which appears exactly once, return the single element that appears only once.

You must implement a solution with:

Linear runtime complexity
Constant extra space

Examples

Example 1:

Input: nums = [2,2,3,2]
Output: 3

Example 2:

Input: nums = [0,1,0,1,0,1,99]
Output: 99

Constraints

1 <= nums.length <= 3 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
Every element appears exactly three times except one

Intuition

If every number appears three times, and one appears once, we can track bit counts.

But instead of counting each bit individually (using 32 counters), we simulate this using bitmasking via two integer variables:

once: bits seen once
twice: bits seen twice

These act like bit buckets to store how many times a bit has been seen.

Key Observation:

Each bit in an integer has only three possible states under mod 3 counting:

Seen 0 times → state 0
Seen 1 time → state 1
Seen 2 times → state 2
After that → reset back to state 0 (like mod 3 cycle)

Approach: Bitmask State Machine (2-bit counter)

We use two variables to simulate a 2-bit counter per bit position.

Let’s denote:

once: stores bits seen once but not twice
twice: stores bits seen twice but not once
When a bit has been seen three times, it gets cleared from both

Transition Logic:

For each number i:

once  = (once ^ i) & ~twice;
twice = (twice ^ i) & ~once;

once ^ i: toggles bits (like XOR)
& ~twice: clears bits already present in twice
⇒ So bits go from 0 → 1 → 2 → 0 cleanly across once and twice

At the end:

The unique number appears only once, so it remains in once

Java Code

class Solution {
    public int singleNumber(int[] nums) {
        int once = 0;
        int twice = 0;
        for (int i : nums) {
            once = (once ^ i) & ~twice;
            twice = (twice ^ i) & ~once;
        }
        return once;
    }
}

Time and Space Complexity

Metric	Value
Time Complexity	O(n)
Space Complexity	O(1)
Explanation	Constant space using two 32-bit integers

Dry Run

Input: `[2, 2, 3, 2]`

Initial: once = 0, twice = 0

i = 2 → once = 2, twice = 0
i = 2 → once = 0, twice = 2
i = 3 → once = 3, twice = 2
i = 2 → once = 1, twice = 0

Final result: once = 3 → the single number

Concept: n-Buckets Bitmasking (Generalization)

When a number appears n times and one appears k times (where k < n), you can generalize this approach using bitwise counters and mod-n logic.

Why is it called "n-buckets"?

Think of it like each bit in the integer has its own bucket counter. For 32-bit integers, there are 32 positions. You’re counting how many times each bit appears across all numbers, and keeping it modulo n.

General Strategy:

For each bit position (0 to 31), count how many times 1 occurs across all numbers.
Take each bit's total mod n
If mod result ≠ 0 → that bit is set in the unique number

This can be implemented either:

Using bit position-wise counters (O(32n) but simple), or
With bitmask simulation, as shown above (efficient O(n) with O(1) space)

Extension for other patterns:

Single Number II (appears once, others thrice) → 2-bit simulation (once, twice)
Single Number III (all appear twice, two appear once) → use XOR trick twice

Conclusion

This is a brilliant bit manipulation problem that demonstrates how to:

Track frequencies using only bitwise operations
Simulate modulo arithmetic via bitmask logic
Solve frequency-based problems in constant space