Single Number II | Bit Manipulation

This comprehensive study note covers the algorithmic journey for solving the Single Number II problem using four distinct approaches—ranging from a naive hash map to an optimal bit-bucket manipulation technique.

1. Problem Statement & Core Objective

The problem requires us to find a unique element in an integer array where every other element appears exactly three times, while the single target element appears exactly once.

Input Array: [5, 5, 5, 2, 4, 4, 4]
Frequencies: 
   - 5 appears 3 times
   - 4 appears 3 times
   - 2 appears 1 time (Target Result)

Output: 2

Note: The elements in the input array are not guaranteed to be clustered together. They can appear in any arbitrary order.

2. Approach 1: The Brute Force Hash Map Solution

Core Idea

The most intuitive approach is to count the frequency of each element using a hash map data structure and then scan the map to find the key whose frequency is equal to 1.

Pseudocode & Implementation Logic

int singleNumber(vector<int>& nums) {
    unordered_map<int, int> freqMap;
    
    // Step 1: Populate frequency map
    for (int num : nums) {
        freqMap[num]++;
    }
    
    // Step 2: Iterate through map to find element with frequency 1
    for (auto& pair : freqMap) {
        if (pair.second == 1) {
            return pair.first;
        }
    }
    return -1;
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(n \log m + m)$ or $\mathcal{O}(n)$ using an unordered map, where $n$ is the number of elements in the array and $m$ is the number of unique elements ($m \approx \frac{n}{3} + 1$).
• Space Complexity: $\mathcal{O}(m)$ to store unique elements in the hash map.

3. Approach 2: Bitwise Count Manipulation (Bit-by-Bit Analysis)

Core Mental Model / Analogy

Instead of counting whole numbers, we examine numbers at the bit level across all 32 bit positions of an integer.

Step-by-Step Evolution

1. Iterate through all bit positions from 0 to 31.
2. For each bit index, count how many numbers in the array have that specific bit set.
3. If the total count of set bits modulo 3 equals 1 (count % 3 == 1), it means the single unique number has its bit set at this position.
4. Reconstruct the answer variable using bitwise OR and left-shift operations.

Code Implementation

int singleNumber(vector<int>& nums) {
    int ans = 0;
    for (int bitIndex = 0; bitIndex < 32; bitIndex++) {
        int count = 0;
        for (int i = 0; i < nums.size(); i++) {
            // Check if the bitIndex-th bit is set
            if ((nums[i] & (1 << bitIndex)) != 0) {
                count++;
            }
        }
        // If count is not a multiple of 3, this bit belongs to the single number
        if (count % 3 != 0) {
            ans = ans | (1 << bitIndex);
        }
    }
    return ans;
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(32 \times n) = \mathcal{O}(n)$, where $n$ is the array size. The inner loop runs exactly 32 times for every element.
• Space Complexity: $\mathcal{O}(1)$ as we only use a few integer variables (ans, count, bitIndex).

4. Approach 3: Sorting and Linear Scan

Core Idea

If we sort the array first, identical elements will cluster together in groups of three. The single element will break this contiguous grouping pattern.

Sorted Array: [1, 1, 1, 2, 4, 4, 4]
Indices:       0  1  2  3  4  5  6

- Checking index 3 (value 2): nums[3] != nums[2] (2 != 1)
- Mismatch found! Therefore, nums[3 - 1] (or adjacent group inspection) reveals the outlier.

Step-by-Step Evolution

1. Sort the nums array in ascending order: $\mathcal{O}(n \log n)$.
2. Iterate through the array starting from index 1, stepping by 3 positions to check cluster boundaries.
3. If nums[i] != nums[i - 1], the single element has disrupted the triplet, meaning nums[i - 1] is our target.
4. Handle corner cases (e.g., if the single element is at the very beginning or the very end of the array).

Code Implementation

int singleNumber(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return nums[0];
    
    sort(nums.begin(), nums.end());
    
    // Check if single element is at the start
    if (nums[0] != nums[1]) return nums[0];
    
    // Traverse stepping by 3
    for (int i = 1; i < n; i += 3) {
        if (nums[i] != nums[i - 1]) {
            return nums[i - 1];
        }
    }
    
    // If no mismatch found in-between, the last element is the single number
    return nums[n - 1];
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(n \log n + \frac{n}{3}) = \mathcal{O}(n \log n)$ due to sorting.
• Space Complexity: $\mathcal{O}(1)$ auxiliary space (ignoring sorting stack space).
• Disadvantage: Modifies (distorts) the original input array order.

5. Approach 4: Optimal Bit-Bucket State Machine (The Ultimate Solution)

Core Mental Model: The Three-Bucket Concept

To achieve optimal $\mathcal{O}(n)$ time and $\mathcal{O}(1)$ space without sorting or frequency maps, we design a bit-manipulation state machine using two tracking variables: ones and twos.

• ones: Holds bits that have appeared once (modulo 3).
• twos: Holds bits that have appeared twice (modulo 3).
• Implicit threes: When a bit appears for the third time, it gets cleared from both ones and twos.

State Transition Logic per Number

1. ones update: Add current number to ones using XOR, only if it is not currently present in twos (& ~twos).
2. twos update: Add current number to twos using XOR, only if it is not currently present in ones (& ~ones).

Code Implementation

int singleNumber(vector<int>& nums) {
    int ones = 0;
    int twos = 0;
    
    for (int num : nums) {
        // Add to 'ones' if not in 'twos', then clear from 'ones' if already present
        ones = (ones ^ num) & ~twos;
        
        // Add to 'twos' if not in 'ones', then clear from 'twos' if already present
        twos = (twos ^ num) & ~ones;
    }
    
    return ones; // 'ones' holds the single element remaining after all triplet cancellations
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(n)$ — Single pass over the array, executing constant-time bitwise operations.
• Space Complexity: $\mathcal{O}(1)$ — Uses only two integer variables (ones and twos).

6. Comparative Synthesis of All Four Approaches

7. Summary and Key Takeaways

• Problem Generalization: The bit-counting and bit-bucket techniques can be generalized to solve any Single Number variant where elements appear $k$ times except for one.
• Bit-Level Independence: Bit manipulation works seamlessly because operations occur independently across all 32 bit positions without interference between adjacent bit indices.
• Space-Time Tradeoffs: While brute-force hashing and sorting are easier to conceptualize on the spot, bitwise state machines provide optimal $\mathcal{O}(n)$ time and $\mathcal{O}(1)$ space complexity.
• The Power of XOR & Negation: Combining XOR (^) with bitwise NOT (~) allows us to simulate state toggling and conditional bit-clearing without conditional branching (if-else).
• Interview Strategy: Always explain the Brute Force or Bit-Counting approach first to demonstrate logical progression before presenting the optimal $\mathcal{O}(n)$ bit-bucket state machine solution.