Solution Explanation for LeetCode 136: Single Number

This problem asks to find the unique number in an array where all other numbers appear twice. The most efficient solution leverages the properties of the bitwise XOR (^) operator.

Understanding the XOR Operator:

The XOR operator has two crucial properties for this problem:

1. Identity Element: x ^ 0 = x (XORing with 0 leaves the number unchanged).
2. Involution: x ^ x = 0 (XORing a number with itself results in 0).

Algorithm:

The algorithm is remarkably simple:

1. Initialize a variable result to 0.
2. Iterate through the input array nums.
3. For each number num in nums, perform a XOR operation between result and num: result = result ^ num.

Because of the involution property, when a number appears twice, its XOR operations cancel each other out, resulting in 0. The unique number, appearing only once, will remain in result.

Time and Space Complexity:

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once.
• Space Complexity: O(1). We use only a constant amount of extra space to store the result variable.

Code Implementation (Python):

def singleNumber(nums):
    result = 0
    for num in nums:
        result ^= num
    return result
 
#Example Usage
nums = [2,2,1]
print(singleNumber(nums)) # Output: 1
 
nums = [4,1,2,1,2]
print(singleNumber(nums)) # Output: 4

Code Implementation (Java):

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
}

Code Implementation (C++):

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
};

Other Languages: The implementations in other languages (JavaScript, Go, TypeScript, Rust, C#, C, Swift etc.) follow the same basic structure, iterating through the array and applying the XOR operation. The specific syntax may vary slightly depending on the language, but the core logic remains consistent. The use of reduce function as shown in some solutions offers a more concise way to express the same logic.

Alternative Approaches (Less Efficient):

While the XOR approach is optimal, alternative approaches exist but are less efficient:

• Hash Table: You could use a hash table (dictionary in Python) to count the occurrences of each number. This would have O(n) time complexity but O(n) space complexity, violating the constraint of constant extra space.
• Sorting: Sorting the array and then iterating to find the unique element would require O(n log n) time complexity.

In summary, the bitwise XOR operation provides an elegant and highly efficient solution to this problem, meeting the requirements of linear time and constant space complexity.