137. Single Number II¶

Question¶

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

You must implement a solution with a linear runtime complexity ($O(n)$) and use only constant extra space ($O(1)$).

Solution¶

Pattern¶

Bitwise State Machine (Parallel Bit Counting) Simulating a digital logic circuit using bitwise operations (XOR, AND, NOT) to count bit frequencies modulo $k$ across all elements simultaneously.

How to Identify¶

Elements appear $k$ times (where $k > 2$), and exactly one element appears a different number of times.
Rigid constraints mandate $O(1)$ auxiliary space, precluding the use of frequency hash tables.
The requirement calls for low-level, high-performance bitstream parsing.

Description¶

Step-by-step explanation:

Step 1: Establish Bit Trackers. To count up to 3 occurrences per bit position, a 3-state transition system ($00 \rightarrow 01 \rightarrow 10 \rightarrow 00$) is needed. This requires two variables: ones and twos.
Step 2: Initialize States. Initialize both tracking registers ones and twos to 0.
Step 3: Linear Pass. Loop through each number num in the array exactly once.
Step 4: Update States. For each number, update the bits in our tracking states using bitwise logic gates:
ones = (ones ^ num) & ~twos; (Capture bits appearing for the first time, or resetting if appearing a third time).
twos = (twos ^ num) & ~ones; (Capture bits appearing for the second time).
Step 5: Output. Elements appearing three times cycle fully back to state 00. The unique element leaves its bits trapped in the first state container. Return ones.

The Intuition¶

Think of this as constructing a row of 3-way cyclic light switches for each of the 32 bit positions.

Every time a 1 bit hits a position, its switch clicks forward: $$\text{State } 00 \text{ (Seen 0 times)} \rightarrow \text{State } 01 \text{ (Seen 1 time)} \rightarrow \text{State } 10 \text{ (Seen 2 times)} \rightarrow \text{State } 00 \text{ (Seen 3 times)}$$

The expression ones ^ num toggles the bit between appearing an odd and even number of times.
The masking expressions & ~twos and & ~ones act as safety interlocks. They prevent a bit from activating state 1 if it is currently moving into state 2, or resetting state 2 if it is cycling back down to 0.
Since all bits are processed in parallel via the CPU's word register, we run this light switch board across the entire stream in a single pass.

Complexity¶

Label	Worst	Average
Time Complexity	$O(n)$	$O(n)$
Space Complexity	$O(1)$	$O(1)$

Time Complexity¶

$O(n)$. The array is parsed in a single linear pass. Each element triggers only 6 basic bitwise operations, running with a constant factor coefficient of 1.

Space Complexity¶

$O(1)$. Auxiliary memory allocation is locked to two local tracking primitive integers (ones and twos), independent of array scaling.

Code¶

class Solution {
    /**
     * Finds the element that appears exactly once when all others appear three times.
     * Uses bitwise parallel state reduction to optimize the constant execution overhead.
     */
    public int singleNumber(int[] nums) {
        // Tracks bits that have appeared 1 time (modulo 3)
        int ones = 0; 
        // Tracks bits that have appeared 2 times (modulo 3)
        int twos = 0; 

        for (int num : nums) {
            // Update 'ones' only if the bit isn't already part of a pair tracked in 'twos'
            ones = (ones ^ num) & ~twos;

            // Update 'twos' only if the bit isn't actively held in the newly calculated 'ones'
            twos = (twos ^ num) & ~ones;
        }

        // Elements seen 3 times clear out to 0. The single item remains in 'ones'.
        // If the unique item appeared twice, we would return 'twos'.
        return ones;
    }
}

Caveats¶

Fragile State Alignment: The ordering of the statements is critical. If you alter the assignment sequencing without adjusting the interlocking components (e.g., trying to calculate twos first using the historical ones), the state logic will collapse.
Strict Multiplicity: This exact bitwise combination logic is hardcoded specifically for frequencies of three (3). It cannot handle unaligned arrays without altering the state truth tables entirely.

Concepts to Think About¶

Two's Complement Representation: Understanding why signed integers and bit shifting behave consistently at the register boundaries.
K-Bit Counter Simulation: Generalizing bit counters using combinations of boolean expressions derived via Karnaugh Maps (K-Maps).
Parallel Processing via Word Size: How bitwise gates leverage the processor's underlying architectural data registers to avoid itemized indexing loops.

Logical Follow-up¶

Question: What if the unique element appears exactly twice instead of once?

Solution: The elements appearing three times will cycle back to 00. The element appearing twice will be caught in state 10. Therefore, you would return twos instead of ones.

Question: How can we generalize this approach if every element appears k times and one appears exactly once?

Solution: Determine the number of tracking bits required (⌈log₂(k)⌉). Maintain m variables (bit1, bit2, ... bitM). Use a bitwise mask representing the binary layout of k to identify when the counters reach k, then apply an AND NOT operation across all tracking variables to clear the state back to zero.

Label	Worst	Average
Time Complexity	\(O(n)\)	\(O(n)\)
Space Complexity	\(O(1)\)	\(O(1)\)