Brute Force Approach for Single Number II

The most intuitive way to solve this is to count the frequency of every number in the array. We can use a hash map (dictionary) to store the counts.

Pseudo-code:

text
create a hash map named counts
for each number in nums:
    increment counts[number]

for each number in counts:
    if counts[number] == 1:
        return number

Why it fails: While this approach is correct and runs in linear time $O(N)$, it requires $O(N)$ space to store the hash map. The problem explicitly restricts us to constant extra space $O(1)$. Therefore, for large inputs (up to $3 \cdot 10^4$ elements), the memory usage is suboptimal relative to the constraints, making this approach invalid for the specific requirements of the interview question.

Core Insight for Single Number II

The core insight is to treat the integers as vectors of 32 bits and process each bit position independently.

In the standard "Single Number" problem (where duplicates appear twice), we use XOR because XOR acts as addition modulo 2 without carry ($1 + 1 = 0$). Here, duplicates appear three times. We need an operation that acts as addition modulo 3.

If we sum the bits at the $i$-th position for all numbers:

• If the single number has a 0 at bit $i$, the sum will be $3k + 0$ (since all other numbers appear in triplets).
• If the single number has a 1 at bit $i$, the sum will be $3k + 1$.

Therefore, if we sum the bits at every position and take the result modulo 3, the remainder is exactly the bit of the single number.

Visual Description: Imagine a digital logic circuit or a state machine processing the stream of numbers. For any specific bit position (e.g., the 0-th bit), we start at state 00. When we encounter a 1, the state transitions to 01 (seen once). Another 1 moves it to 10 (seen twice). A third 1 resets it back to 00 (seen three times). This cycle repeats, effectively filtering out all numbers appearing three times, leaving only the bits of the unique number in the 01 state.

Execution Flow

Let's trace the algorithm with nums = [2, 2, 3, 2]. Binary representations: 2 is 0010, 3 is 0011.

Initialization: ones = 0000 twos = 0000

Step 1: Process 2 (0010)

• Update ones: (0000 ^ 0010) & ~0000 = 0010 (Bit 1 seen once)
• Update twos: (0000 ^ 0010) & ~0010 = 0000 (Bit 1 not seen twice yet)
• State: ones=0010, twos=0000

Step 2: Process 2 (0010)

• Update ones: (0010 ^ 0010) & ~0000 = 0000 (Bit 1 cleared from ones)
• Update twos: (0000 ^ 0010) & ~0000 = 0010 (Bit 1 moved to twos)
• State: ones=0000, twos=0010

Step 3: Process 3 (0011)

• Update ones: (0000 ^ 0011) & ~0010 = 0011 & 1101 = 0001
  • Bit 0 of 3 enters ones.
  • Bit 1 of 3 tries to enter ones, but twos has bit 1 set, so it is blocked.
• Update twos: (0010 ^ 0011) & ~0001 = 0001 & 1110 = 0000
  • Wait, let's re-evaluate carefully bitwise.
  • Correct Logic check:
    • ones (new) captures bits appearing 1st time or 4th time.
    • twos (new) captures bits appearing 2nd time or 5th time.
  • Let's stick to the formula:
    • new_ones = (0000 ^ 0011) & ~0010 -> 0011 & 1101 -> 0001. (Bit 0 is now seen once).
    • new_twos = (0010 ^ 0011) & ~0001 -> 0001 & 1110 -> 0000. (This transition logic is slightly complex to trace manually without the full truth table, but effectively Bit 1 was in twos, incoming is 1, so it should reset to 0. Bit 0 was 0, incoming is 1, goes to ones).
    • Actually, let's correct the trace for twos. The formula uses the updated ones.
    • ones became 0001.
    • twos = (0010 ^ 0011) & ~0001 = 0001 & 1110 = .
• State: ones=0001, twos=0000

Step 4: Process 2 (0010)

• Update ones: (0001 ^ 0010) & ~0000 = 0011
• Update twos: (0000 ^ 0010) & ~0011 = 0000
• Final State: ones=0011 (Wait, this trace is slightly off because the example numbers are interleaved. The single number is 3 (0011). The 2s should cancel out).

Let's re-verify the logic of the single number 3 (0011). The 2s appear 3 times. Their bits at position 1 will cycle $1 \to 2 \to 0$. They vanish. The 3 appears 1 time. Its bits at position 0 and 1 will enter state 1. Result ones should be 3.

Final result is returned from ones.

Proof of Correctness

The algorithm implements a modulo-3 counter for each bit position $i$. Let $S_i$ be the sum of the $i$-th bits of all numbers in the array. We can write $S_i = 3 \cdot k + b_i$, where $b_i$ is the $i$-th bit of the single number (0 or 1), and $k$ is the number of groups of three. Our variables ones and twos maintain the state of this count:

• If $S_i \pmod 3 = 1$, the $i$-th bit of ones is 1 and twos is 0.
• If $S_i \pmod 3 = 2$, the $i$-th bit of ones is 0 and is 1.
• If $S_i \pmod 3 = 0$, both are 0.

Since the unique element appears exactly once, the final count for its active bits will be $1 \pmod 3$. Thus, the variable ones will hold the exact bitmask of the single number.

Reference Implementation

C++ Solution for LeetCode 137

cpp
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ones = 0;
        int twos = 0;
        
        for (int num : nums) {
            // Update 'ones' with the new number, but remove bits that are now in 'twos'
            ones = (ones ^ num) & ~twos;
            
            // Update 'twos' with the new number, but remove bits that are now in 'ones'
            twos = (twos ^ num) & ~ones;
        }
        
        return ones;
    }
};

Java Solution for LeetCode 137

java
class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0;
        int twos = 0;
        
        for (int num : nums) {
            // 'ones' captures bits that have appeared 1st time or 4th time, etc.
            // If a bit is already in 'twos', it means it has appeared twice.
            // Adding it again (3rd time) should clear it from both.
            ones = (ones ^ num) & ~twos;
            
            // 'twos' captures bits that have appeared 2nd time or 5th time, etc.
            // We use the updated 'ones' to ensure a bit isn't in both states.
            twos = (twos ^ num) & ~ones;
        }
        
        return ones;
    }
}

Python Solution for LeetCode 137

python
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ones = 0
        twos = 0
        
        for num in nums:
            # Update 'ones' to track bits seen once
            # If bit is in 'twos', it means it was seen twice before, so now 3 times -> clear it
            ones = (ones ^ num) & ~twos
            
            # Update 'twos' to track bits seen twice
            # If bit is in 'ones' (updated), it means it is seen once now, so not twice
            twos = (twos ^ num) & ~ones
            
        return ones