L5. Single Number-I | Bit Manipulation

This chapter explores the "Single Number" problem, a classic algorithmic puzzle that can be efficiently solved using bitwise operations. We analyze the problem requirements, look at a naive frequency-mapping approach, examine its complexity trade-offs, and derive an optimal linear-time, constant-space solution utilizing the XOR bitwise operator.

1. Problem Statement and Objective

The objective of the Single Number problem is to find a unique element in an array where all other elements appear exactly twice.

• Input: An integer array nums of size n where every element appears twice except for one element which appears only once.
• Output: The single element that appears only once.

Example Walkthrough

Consider the following input array:

nums = [4, 1, 2, 1, 2]

• The number 1 appears twice.
• The number 2 appears twice.
• The number 4 appears once.
• Expected Return Value: 4.

2. Why Do We Need a Better Approach? (Status Quo)

When presented with this problem in an interview, the initial intuition often relies on auxiliary data structures to track frequencies. While correct, this approach incurs unnecessary memory overhead. We need to evaluate whether we can eliminate extra space by leveraging fundamental properties of binary arithmetic.

3. The Naive Approach: Hashing and Frequency Counting

The most straightforward way to solve this problem is to count the occurrences of each element using a Hash Map.

Algorithm Steps

1. Initialize an empty hash map (or dictionary) to store element-frequency pairs (key: element, value: count).
2. Traverse the nums array from index 0 to n - 1.
3. For each element, increment its corresponding count in the map.
4. After populating the map, iterate through its keys/values to find the element whose count is equal to 1.
5. Return that element.

Pseudocode (C++ Style)

int singleNumber(vector<int>& nums) {
    unordered_map<int, int> freqMap;
    int n = nums.size();
    
    // Step 1: Populate frequency map
    for(int i = 0; i < n; i++) {
        freqMap[nums[i]]++;
    }
    
    // Step 2: Find the element with a count of 1
    for(auto it : freqMap) {
        if(it.second == 1) {
            return it.first;
        }
    }
    
    return -1; // Fallback if no single number exists
}

Complexity Analysis of the Naive Approach

• Time Complexity:
  • Inserting n elements into an unordered_map takes $\mathcal{O}(n)$ on average (or $\mathcal{O}(n \log m)$ if using an ordered map, where $m$ is the map size).
  • Iterating through the map takes $\mathcal{O}(m)$ time, where $m$ is the number of unique elements.
  • Overall Time Complexity: $\mathcal{O}(n) \text{ or } \mathcal{O}(n \log m)$.
• Space Complexity: $\mathcal{O}(m)$, where $m = \frac{n}{2} + 1$ because almost all elements appear in pairs except for the single unique element.

Note: An interviewer will typically reject this solution as optimal because it utilizes $\mathcal{O}(n)$ auxiliary space. We need a solution that achieves $\mathcal{O}(1)$ auxiliary space.

4. Core Mental Model: The XOR Operator

To achieve an optimal solution, we turn to bitwise manipulation, specifically the XOR (Exclusive OR) operator (represented in code as ^).

Fundamental Properties of XOR

1. Self-Cancellation (Inverse Property): XORing any number with itself results in 0.

2. Identity Property: XORing any number with 0 returns the number itself.

3. Commutative and Associative: The order and grouping of XOR operations do not matter.

Real-Life Analogy: Pairing and Cancelling Out

Imagine a room where people pair up and leave. Every person has an identical twin who enters with them, except for one person who came alone. If everyone cancels out their identical twin when they meet, the only person left standing at the end of the night is the one without a pair.

5. Step-by-Step Evolution of the Optimal Solution

If we take the XOR sum of all elements in our array, the duplicate elements will pair up and cancel each other out to 0, leaving only the unique element.

Mathematical Breakdown of Example

Given nums = [4, 1, 2, 1, 2]:

Using the commutative property to group identical numbers together:

Applying the self-cancellation property ($1 \oplus 1 = 0$ and $2 \oplus 2 = 0$):

Applying the identity property ($0 \oplus 4 = 4$):

6. Optimal Solution Implementation

Here is the clean, production-grade implementation of the optimal approach in C++:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int xorSum = 0;
        
        // Traverse through all elements and compute cumulative XOR
        for(int i = 0; i < nums.size(); i++) {
            xorSum = xorSum ^ nums[i];
        }
        
        // The remaining value is the unique single number
        return xorSum;
    }
};

Flow Walkthrough

7. Comparative Analysis of Approaches

8. Summary and Key Takeaways

• Problem Constraint Exploitation: The guarantee that every number appears twice except for one allows us to look for cancellation patterns rather than raw frequency counts.
• XOR Operator Power: The XOR operation (^) is commutative, associative, and yields 0 when an operand is XORed with itself ($a \oplus a = 0$).
• Elimination of Duplicates: Cumulative XORing of an entire array collapses all paired elements to 0.
• Identity Retention: XORing with 0 preserves the remaining unmatched value ($0 \oplus a = a$).
• Time Complexity Optimization: Traversing the array once results in an optimal runtime of $\mathcal{O}(n)$.
• Space Complexity Optimization: Storing the cumulative result in a single primitive variable reduces auxiliary space to $\mathcal{O}(1)$.
• Interview Standard: Recognizing bit manipulation shortcuts separates brute-force thinking from optimal algorithmic engineering.