Single Number III | Bit Manipulation

This chapter covers the optimal solution to finding two unique non-repeating numbers in an array where every other element appears exactly twice. Building upon the foundational Single Number I and Single Number II patterns, this approach leverages advanced bitwise operations to achieve optimal $O(n)$ time complexity and $O(1)$ auxiliary space without relying on external hashing structures.

1. Problem Statement and Status Quo

Given an array of integers nums, every number appears twice except for two distinct numbers that appear only once. Our task is to find and return those two distinct numbers in any order.

Example Walkthrough

• Input Array: [2, 4, 2, 6, 3, 7, 7, 3]
• Frequencies:
  • 2: Appears twice
  • 7: Appears twice
  • 3: Appears twice
  • 4: Appears once
  • 6: Appears once
• Expected Output: [4, 6] (or [6, 4])

2. Naive Approach: Hashing and Frequency Maps

When first encountering this problem in an interview, the most intuitive brute-force strategy is to use a frequency map.

Algorithm Steps

1. Initialize a hash map to store (number, frequency) pairs.
2. Traverse the nums array and increment the frequency count for each number.
3. Traverse the hash map keys to find the two keys whose frequency equals 1.
4. Collect these keys into a list/vector and return them.

Pseudocode Implementation

vector<int> singleNumber(vector<int>& nums) {
    unordered_map<int, int> freqMap;
    for (int num : nums) {
        freqMap[num]++;
    }
    
    vector<int> ans;
    for (auto& pair : freqMap) {
        if (pair.second == 1) {
            ans.push_back(pair.first);
        }
    }
    return ans;
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(n \log m + m)$ (where n is the array size and m is the number of unique elements in the map). If using an unordered map, average time is $\mathcal{O}(n)$.
• Space Complexity: $\mathcal{O}(m)$ auxiliary space to store elements in the hash map, where m = \frac{n}{2} + 1.

3. The Interviewer's Objection: Moving Beyond Extra Space

While hashing solves the problem, interviewers will typically reject $\mathcal{O}(m)$extra space and demand an **$\mathcal{O}(1)$ space complexity** solution. To achieve this, we must transition from external data structures to bitwise operators, specifically leveraging the properties of the XOR (^) operator and bucket separation.

4. Core Mental Model: The XOR Accumulation

The XOR operator possesses a critical algebraic property:

• x ^ x = 0 (Any number XORed with itself cancels out to zero).
• x ^ 0 = x (Any number XORed with zero remains unchanged).
• XOR is commutative and associative.

Step 1: Total XOR Operation

If we take the XOR sum of every single element in the nums array:

Total XOR = (2 ^ 2) ^ (7 ^ 7) ^ (3 ^ 3) ^ 14 ^ 4
          = 0 ^ 0 ^ 0 ^ (14 ^ 4)
          = 14 ^ 4

All paired elements (2, 7, 3) cancel each other out, leaving us exclusively with the XOR sum of the two unique target numbers (14 and 4).

Let's look at their binary representations:

• 14 in binary: 1110 (which is 8 + 4 + 2)
• 4 in binary: 0100 (which is 4)

Computing 14 ^ 4:

The resulting value 10 is the XOR sum of our two distinct target numbers.

Crucial Observation: Because the two numbers are distinct, their XOR result (10) cannot be 0. This means there must be at least one bit position where their binary digits differ (1 vs 0). In our case, the 1st bit (from the right) and 3rd bit differ.

5. Isolating the Rightmost Set Bit

To separate our two target numbers (14 and 4) into two distinct groups, we can pick any differing bit position. The cleanest, standard practice in bit manipulation is to isolate the rightmost set bit (the rightmost 1).

The Rightmost Bit Formula

As established in previous bit manipulation techniques, a number combined with its negation or minus-one state isolates its lowest set bit:

Rightmost Bit = zor & (-zor)

Alternatively, using the standard bitwise trick:

int rightmost = (zor & (zor - 1)) ^ zor;

Applying this to our XOR result (10 or binary 1010):

• 1010 isolated at the rightmost set bit yields 0010 (2 in decimal).

6. The Bucket Partition Strategy

Now that we have isolated a differing bit position (2), we can conceptually divide all array elements into two separate buckets:

• Bucket 1: Numbers where this specific bit position is set (1).
• Bucket 2: Numbers where this specific bit position is unset (0).

Why This Works Magically:

1. Separation of Targets: Our two unique numbers (14 and 4) have different bits at this position. Therefore, 14 will fall into Bucket 1, and 4 will fall into Bucket 2.
2. Pair Preservation: All other numbers appear twice. Because identical numbers have identical binary representations, both instances of any duplicate number will always land in the exact same bucket.

7. Step-by-Step Flow Walkthrough

Let's trace how elements populate our two conceptual buckets on-the-fly using two integer variables (bucket1 and bucket2) instead of arrays.

At the end of traversal:

• Bucket 1 contains all paired duplicates (which cancel out to 0) plus 14. Result: 14.
• Bucket 2 contains all paired duplicates (which cancel out to 0) plus 4. Result: 4.

8. Optimized Code Implementation

Here is the robust, production-grade implementation in C++ incorporating the integer overflow safety check.

#include <vector>

class Solution {
public:
    std::vector<int> singleNumber(std::vector<int>& nums) {
        // Step 1: Get the XOR sum of all elements
        long long zor = 0; // Using long long to prevent overflow edge cases
        for (int num : nums) {
            zor ^= num;
        }

        // Step 2: Find the rightmost set bit
        // zor & (-zor) isolates the lowest set bit
        long long rightmost = (zor & (zor - 1)) ^ zor;

        int bucket1 = 0;
        int bucket2 = 0;

        // Step 3: Partition into two buckets and XOR on the fly
        for (int num : nums) {
            if ((num & rightmost) != 0) {
                bucket1 ^= num;
            } else {
                bucket2 ^= num;
            }
        }

        return {bucket1, bucket2};
    }
};

9. Real-World Pitfalls & Integer Overflow Edge Case

The Minimum Integer Trap (-2^{31})

In 32-bit signed integer systems:

• Minimum value: -$2^{31}$ (-2147483648)
• Maximum value: $2^{31} - 1$ (2147483647)

The Bug: If your total XOR sum (zor) happens to evaluate to the minimum possible integer (-2147483648), attempting to compute zor - 1 results in underflow (2147483647 is valid, but working with bit masks on standard 32-bit signed boundaries can trigger undefined overflow behavior depending on the language).

The Fix: Always declare your accumulator zor as a long long (or 64-bit integer equivalent) in languages like C++ and Java. This guarantees that arithmetic operations like zor - 1 execute safely without boundary violations.

10. Summary and Key Takeaways

• Problem Reduction: Reducing the two-unique-number search to XOR accumulation isolates the combined XOR state (X ^ Y).
• Bit Difference Principle: Two distinct numbers guarantee at least one differing bit position, enabling logical separation.
• Bucket Separation: Isolating the rightmost set bit via (zor & -zor) provides a deterministic discriminator to partition numbers into two isolated XOR streams.
• Duplicate Cancellation: Because identical numbers always route to the exact same bucket, they naturally cancel themselves out via XOR (x ^ x = 0).
• Space Optimization: Utilizing scalar XOR variables (bucket1, bucket2) eliminates external hash maps, dropping auxiliary space complexity to absolute constant bounds.
• Time Complexity: $\mathcal{O}(n)$ time as it requires exactly two linear passes over the input array.
• Space Complexity: $\mathcal{O}(1)$ auxiliary space.
• Overflow Awareness: Utilizing long long for XOR accumulators protects against edge-case integer overflows at boundaries like -2^{31}.