Home/Questions/Q 3536
Next
In Process

RTSALL Latest Articles

aarav0
Asked: 2026-09-11T09:53:26-05:00 In: ,

How to find the Single Number when all others appear 3 times using a Digital Logic State Machine?

When elements in an array appear twice except one, we can simply XOR all numbers together. But what if every element appears three times, except for a single number that appears once?

The standard hash-map solution uses O(N) space. How can we solve this in O(N) time and O(1) space using digital logic gates (AND, OR, NOT, XOR) and a two-variable state machine (ones and twos)?

Leave an answer

You must login to add an answer.

Need An Account,

2 Answers

  1. Abhay Tiwari
    Begginer

    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:

    Current State (twos, ones)Input Bit (x)Next State (twos, ones)Explanation
    0, 000, 0Seen 0 times
    0, 010, 1Seen 1 time
    0, 100, 1Unchanged
    0, 111, 0Seen 2 times
    1, 001, 0Unchanged
    1, 010, 0Seen 3 times → RESETS TO 0!

    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.
    • 0
  2. Abhishek
    Begginer

    Here is the C++20 digital logic state machine for finding the unique number when all other numbers appear 3 times.

    Modern C++20 Solution (Fully Runnable)

    #include <iostream>
#include <vector>

int singleNumber(const std::vector<int>& nums) {
    int ones = 0;
    int twos = 0;

    for (int x : nums) {
        // Bit transitions: 0 -> 1 -> 2 -> 0
        ones = (ones ^ x) & (~twos);
        twos = (twos ^ x) & (~ones);
    }
    return ones;
}

int main() {
    std::vector<int> nums = {0, 1, 0, 1, 0, 1, 99};
    std::cout << "Single Number: " << singleNumber(nums) << "n"; // Expected: 99
    return 0;
}

    Complexity: Strictly O(N) time and O(1) space (2 integer variables).

    • 0