Brute Force Approach for Single Number

A naive approach to solving the Single Number problem involves tracking the frequency of each element to identify the one that appears once. This is typically achieved using a Hash Map (or Hash Set).

Pseudo-code:

1. Initialize an empty Hash Map.
2. Iterate through the array nums.
3. If an element is already in the map, remove it (since we found the pair).
4. If the element is not in the map, add it.
5. After the loop, the map will contain exactly one element. Return it.

Complexity Analysis:

• Time Complexity: $O(n)$. We traverse the array once, and hash map operations are $O(1)$ on average.
• Space Complexity: $O(n)$. In the worst case, the map stores up to $n/2 + 1$ elements.

Why it fails: While this brute force method satisfies the linear time requirement, it violates the constant space constraint. Allocating memory proportional to the input size is not permitted. Alternatively, a brute force approach using nested loops to compare every number with every other number would satisfy the space constraint ($O(1)$) but fail the time constraint ($O(n^2)$), likely resulting in a Time Limit Exceeded (TLE) error on large inputs.

Core Insight for Single Number

The transition from a brute force approach to the optimal solution requires understanding the mathematical properties of the XOR (Exclusive OR) operation, denoted as $\oplus$.

The XOR operation has three critical properties that make it the perfect tool for this problem:

1. Identity: $a \oplus 0 = a$ (XORing with 0 leaves the number unchanged).
2. Self-Inverse: $a \oplus a = 0$ (XORing a number with itself results in 0).
3. Commutativity and Associativity: The order in which operations are performed does not matter. $a \oplus b \oplus a$ is the same as $(a \oplus a) \oplus b$.

Key Invariant: Because every number appears exactly twice except for one, if we XOR all numbers in the array together, the duplicate pairs will "annihilate" each other (become 0). The only remaining value will be the single number, effectively $0 \oplus \text{single} = \text{single}$.

Visual Description: Imagine a binary register initialized to 0. As the algorithm iterates through the array, the register updates its state by XORing its current value with the incoming number. When the algorithm encounters the first instance of a number (e.g., 5), specific bits in the register flip. When the second instance of 5 is encountered later in the array, the exact same bits flip again. Since XOR is its own inverse, flipping a bit twice restores it to its original state. Consequently, all bits affected by paired numbers return to 0, while the bits corresponding to the single number remain flipped.

Execution Flow

Consider the input: nums = [4, 1, 2, 1, 2]

1. Initialize: result = 0
2. Index 0 (Value 4):
   • Operation: 0 ^ 4
   • Binary: 000 ^ 100 = 100
   • result is now 4.
3. Index 1 (Value 1):
   • Operation: 4 ^ 1
   • Binary: 100 ^ 001 = 101
   • result is now 5.
4. Index 2 (Value 2):
   • Operation: 5 ^ 2
   • Binary: 101 ^ 010 = 111
   • result is now 7.
5. Index 3 (Value 1):
   • Operation: 7 ^ 1
   • Binary: 111 ^ 001 = 110
   • result is now 6. (Notice how the bits for 1 have been reversed).
6. Index 4 (Value 2):
   • Operation: 6 ^ 2
   • Binary: 110 ^ 010 = 100
   • result is now 4.
7. Final Output: Return 4.

The intermediate values (5, 7, 6) are transient states. The final state guarantees that 1 cancelled 1, 2 cancelled 2, and 4 remains.

Proof of Correctness

Let the array be represented as a set of integers $\{a_1, a_1, a_2, a_2, ..., a_k, a_k, x\}$, where $x$ is the single number and all $a_i$ appear twice.

The algorithm computes the sequential XOR sum: $S = a_1 \oplus a_1 \oplus a_2 \oplus a_2 \oplus ... \oplus a_k \oplus a_k \oplus x$

Due to the commutative and associative properties of XOR, we can rearrange the terms to group identical numbers: $S = (a_1 \oplus a_1) \oplus (a_2 \oplus a_2) \oplus ... \oplus (a_k \oplus a_k) \oplus x$

Applying the self-inverse property ($n \oplus n = 0$): $S = 0 \oplus 0 \oplus ... \oplus 0 \oplus x$

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

Thus, the algorithm is mathematically guaranteed to return the single number.

Reference Implementation

C++ Solution for LeetCode 136

cpp
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        // Iterate through the vector, applying XOR to the accumulator
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
};

Java Solution for LeetCode 136

java
class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        // Iterate through the array, applying XOR to the accumulator
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
}

Python Solution for LeetCode 136

python
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        # Iterate through the list, applying XOR to the accumulator
        for num in nums:
            result ^= num
        return result