This problem is a masterpiece of digital circuit design translated into software code. Let’s design the state machine from first principles.

1. The Three States of a Bit

For any bit position, as we scan numbers in the array, how many times can we see a 1?

• Seen 0 times → Count = 0
• Seen 1 time → Count = 1
• Seen 2 times → Count = 2
• Seen 3 times → Resets back to 0!

To represent 3 distinct states (0, 1, and 2), we need 2 bits of memory! Let’s name them:

• twos (the high bit)
• ones (the low bit)

2. The Truth Table

When a new bit x arrives from the current number:

3. Deriving the Logic Gates

From the truth table:

• ones = (ones ^ x) & (~twos)
• twos = (twos ^ x) & (~ones)

When the full array has been scanned:

• Every element that appeared 3 times completed the full cycle $(0 o 1 o 2 o 0)$ and returned both bits to 0.
• The single element that appeared 1 time transitioned from $0 o 1$. Its bits are left recorded inside ones!

Clean Python 3.12 Implementation

def single_number(nums: list[int]) -> int:
    """Finds element appearing once while others appear 3 times in O(N) time and O(1) space."""
    ones = 0
    twos = 0

    for x in nums:
        # Update ones: XOR with x, but clear if twos already holds this bit
        ones = (ones ^ x) & ~twos
        # Update twos: XOR with x, but clear if ones now holds this bit
        twos = (twos ^ x) & ~ones

    return ones

Complexity Breakdown

• Time Complexity: O(N). We touch each number once with 4 single-cycle bitwise operations.
• Space Complexity: O(1). Exactly two integer variables living in registers.