Of course! LeetCode 136, "Single Number," is a classic and excellent problem for understanding bit manipulation. Here’s a detailed breakdown, including the optimal solution, explanations, and alternative approaches.

Problem Statement

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity (O(n)) and use only constant extra space (O(1)).

Example 1:

• Input: nums = [2,2,1]
• Output: 1

Example 2:

• Input: nums = [4,1,2,1,2]
• Output: 4

Example 3:

• Input: nums = [1]
• Output: 1

The Optimal Solution: Bitwise XOR (The "Aha!" Moment)

This is the most efficient and elegant solution that directly addresses the problem's constraints.

The Idea

The key is the properties of the bitwise XOR operator (^):

1. Commutative: a ^ b is the same as b ^ a.
2. Associative: a ^ (b ^ c) is the same as (a ^ b) ^ c.
3. Identity: a ^ 0 = a. Any number XORed with 0 is itself.
4. Self-Inverse: a ^ a = 0. Any number XORed with itself results in 0.

Using these properties, if we XOR all the numbers in the array together, the pairs will cancel each other out (result in 0), and the single number will be the result.

Example Walkthrough: nums = [4, 1, 2, 1, 2]

Let's perform the XOR operation from left to right:

• Start with result = 0.
• 0 ^ 4 = 4
• 4 ^ 1 = 5
• 5 ^ 2 = 7
• 7 ^ 1 = 6
• 6 ^ 2 = 4

The final result is 4, which is the single number.

Python Implementation

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        """
        Finds the single number in an array where every other number appears twice.
        This solution uses the bitwise XOR operator, which has the following
        useful properties:
        - a ^ a = 0
        - a ^ 0 = a
        - XOR is commutative and associative.
        By XORing all numbers together, pairs cancel out (a ^ a = 0),
        leaving only the single number (0 ^ single = single).
        Args:
          nums: A list of integers.
        Returns:
          The integer that appears only once.
        """
        result = 0
        for num in nums:
            result ^= num
        return result

Complexity Analysis

• Time Complexity: O(n) We iterate through the list of n elements exactly once. Each XOR operation is a constant time operation.
• Space Complexity: O(1) We only use a single extra variable result to store the final value, regardless of the input size.

Alternative Solutions (For Understanding)

While the XOR solution is the best, it's good to know other approaches and why they might not be optimal.

Hash Set (Using a Dictionary)

This approach is very intuitive and often the first one people think of.

Idea:

1. Create a hash set to store the numbers we have seen.
2. Iterate through the array.
3. For each number, if it's not in the set, add it.
4. If it's already in the set, it's a duplicate, so remove it.
5. After iterating, the set will contain only the single number.

Python Implementation:

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        seen = set()
        for num in nums:
            if num in seen:
                seen.remove(num)
            else:
                seen.add(num)
        return seen.pop() # There will only be one element left

Complexity Analysis:

• Time Complexity: O(n) On average, in, add, and remove operations for a set are O(1). We perform these operations for each of the n elements.
• Space Complexity: O(n) In the worst-case scenario (e.g., the single number is the last one), we might store up to n/2 elements in the set before finding the pairs. This violates the "constant extra space" constraint.

Mathematical Approach (Using Sum)

This approach is clever but has a major drawback: it can lead to integer overflow in some programming languages. Python handles big integers well, so it's less of an issue here, but it's still a good concept to know.

Idea:

1. Calculate the sum of all unique elements in the array.
2. Calculate the sum of all elements in the array.
3. The difference between 2 * sum_of_uniques and sum_of_all will be the single number.
   • 2 * (a + b + c + ... + single) - (a + a + b + b + c + c + ... + single)
   • This simplifies to 2*single - single = single.

Python Implementation:

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # Sum of all unique elements
        sum_unique = sum(set(nums))
        # Sum of all elements (including duplicates)
        sum_all = sum(nums)
        # The difference is the single number
        return 2 * sum_unique - sum_all

Complexity Analysis:

• Time Complexity: O(n) We iterate through the list once to calculate sum(nums). The set(nums) operation also iterates through the list once. The sum() function on the set also iterates through the unique elements.
• Space Complexity: O(n) Creating set(nums) requires space proportional to the number of unique elements, which can be up to n/2. This also violates the constant space constraint.

Summary

For LeetCode 136, the Bitwise XOR solution is the one you should aim for. It's fast, memory-efficient, and demonstrates a powerful understanding of bitwise operations.