Problem Description

You are given a non-empty array of integers called nums. In this array, every element appears exactly twice except for one element that appears only once. Your task is to find and return that single element.

The challenge comes with two important constraints:

• Your solution must run in linear time complexity, meaning O(n) where n is the number of elements in the array
• You must use only constant extra space, meaning O(1) space complexity

For example:

• If nums = [2, 2, 1], the answer would be 1 since it's the only number that appears once
• If nums = [4, 1, 2, 1, 2], the answer would be 4 since all other numbers appear twice

The solution leverages the XOR bitwise operation, which has special properties that make it perfect for this problem. When you XOR a number with itself, the result is 0 (x ^ x = 0), and when you XOR any number with 0, you get the original number back (x ^ 0 = x). By XORing all numbers in the array together, the duplicate pairs cancel each other out (become 0), leaving only the single number that appears once.

Intuition

When we see that every element appears twice except for one, and we need constant space, we need to think about how to identify the unique element without storing information about which numbers we've seen.

The key insight is recognizing that duplicate pairs can somehow "cancel out" each other. If we could find an operation where applying it to two identical numbers results in a neutral element, we could process all numbers and be left with just the unique one.

This is where XOR becomes the perfect tool. XOR has a beautiful mathematical property: a ^ a = 0 for any number a. This means when we encounter the same number twice, they neutralize each other. Additionally, 0 ^ b = b, meaning that XORing with 0 doesn't change the number.

Let's trace through an example to see why this works. If we have [4, 1, 2, 1, 2]:

• Start with 0
• 0 ^ 4 = 4
• 4 ^ 1 = 5
• 5 ^ 2 = 7
• 7 ^ 1 = 6 (this is where the second 1 appears)
• 6 ^ 2 = 4 (this is where the second 2 appears)

But we can rearrange these operations due to XOR's commutative property:

• 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4

The pairs naturally eliminate themselves, leaving only the single number. This approach is elegant because it processes each element exactly once (linear time) and only needs a single variable to store the running XOR result (constant space).

Solution Approach

The solution implements the XOR bitwise operation strategy to find the single number. Here's how the implementation works:

The XOR operation has two crucial properties that make this solution possible:

• Any number XOR 0 remains unchanged: x ^ 0 = x
• Any number XOR itself equals 0: x ^ x = 0

The implementation uses Python's reduce function from the functools module along with the xor operator from the operator module. The reduce function applies XOR cumulatively to all elements in the array.

Here's what happens step by step:

1. The reduce function starts with the first element of nums
2. It then applies XOR between the current result and the next element
3. This process continues through all elements in the array

For example, with nums = [2, 1, 4, 1, 2]:

• First operation: 2
• Second operation: 2 ^ 1 = 3
• Third operation: 3 ^ 4 = 7
• Fourth operation: 7 ^ 1 = 6
• Fifth operation: 6 ^ 2 = 4

Due to XOR's associative and commutative properties, we can conceptually rearrange this as: (2 ^ 2) ^ (1 ^ 1) ^ 4 = 0 ^ 0 ^ 4 = 4

All duplicate pairs XOR to 0, and 0 ^ 4 = 4, leaving us with the single number.

The time complexity is O(n) since we process each element exactly once. The space complexity is O(1) as we only use a constant amount of extra space for the XOR accumulator, regardless of the input size.

Example Walkthrough

Let's walk through a small example with nums = [5, 3, 5] to see how the XOR approach finds the single number.

Step-by-step XOR operations:

1. Start with the first element: result = 5
2. XOR with the second element: result = 5 ^ 3
   • In binary: 101 ^ 011 = 110 (which is 6 in decimal)
3. XOR with the third element: result = 6 ^ 5
   • In binary: 110 ^ 101 = 011 (which is 3 in decimal)

Why this works: Due to XOR's commutative property, we can rearrange the operations:

• 5 ^ 3 ^ 5 = 5 ^ 5 ^ 3 = (5 ^ 5) ^ 3 = 0 ^ 3 = 3

The two 5's cancel each other out (since 5 ^ 5 = 0), leaving us with 3, which is indeed the single number that appears only once.

Another example with more numbers: nums = [7, 2, 7, 9, 2]

Processing in order:

1. result = 7
2. result = 7 ^ 2 = 5
3. result = 5 ^ 7 = 2
4. result = 2 ^ 9 = 11
5. result = 11 ^ 2 = 9

Conceptually regrouping: (7 ^ 7) ^ (2 ^ 2) ^ 9 = 0 ^ 0 ^ 9 = 9

The duplicate pairs (7,7) and (2,2) both XOR to 0, and since 0 ^ 9 = 9, we're left with 9 as our answer. This demonstrates how XOR naturally filters out all paired elements while preserving the single unique element.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because the reduce function with the XOR operation needs to iterate through all elements in the array exactly once, performing a constant-time XOR operation for each element.

The space complexity is O(1). The reduce function only maintains a single accumulator variable to store the intermediate XOR result as it processes the array, regardless of the input size. No additional data structures are created that scale with the input size.

Common Pitfalls

1. Misunderstanding XOR Behavior with Negative Numbers

A common misconception is that XOR might not work correctly with negative numbers or that special handling is needed. In reality, XOR operates on the binary representation of numbers, including their sign bits, so negative numbers work perfectly fine without any special treatment.

Incorrect assumption:

def singleNumber(self, nums: List[int]) -> int:
    # Wrong: Trying to handle negative numbers separately
    result = 0
    for num in nums:
        if num < 0:
            # Unnecessary special handling
            result ^= abs(num)
            # Try to track sign separately (incorrect approach)
        else:
            result ^= num
    return result

Correct approach:

def singleNumber(self, nums: List[int]) -> int:
    # XOR works correctly with negative numbers as-is
    return reduce(xor, nums)

2. Attempting Manual Implementation Without Handling Edge Cases

When implementing XOR manually instead of using reduce, developers often forget to initialize the result properly or make mistakes with the loop structure.

Common mistake:

def singleNumber(self, nums: List[int]) -> int:
    # Wrong: Starting with nums[0] and iterating from index 1 can cause issues
    # if you forget to check array length
    result = nums[0]  # What if nums has only one element?
    for i in range(1, len(nums)):  # This would skip the loop entirely
        result ^= nums[i]
    return result

Better manual implementation:

def singleNumber(self, nums: List[int]) -> int:
    # Initialize with 0 (identity element for XOR)
    result = 0
    for num in nums:
        result ^= num
    return result

3. Confusion About Multiple Single Numbers

The algorithm specifically works when there's exactly ONE number appearing once and all others appearing exactly twice. If there are multiple numbers appearing once or numbers appearing three times, this approach fails.

Problem scenario that breaks the solution:

# This won't work correctly:
nums = [1, 2, 3]  # All appear once - result would be 1^2^3 = 0
nums = [1, 1, 1, 2, 2]  # One appears three times - won't isolate correctly

Solution: For variations like "find two numbers that appear once" or "all numbers appear three times except one", different bit manipulation strategies are needed, such as using bit counting or maintaining multiple XOR accumulators.

4. Overlooking Alternative Implementations

While reduce with xor is elegant, some developers might not be familiar with these functions or might be working in environments where importing additional modules is discouraged.

Alternative implementations without imports:

def singleNumber(self, nums: List[int]) -> int:
    # Using built-in ^ operator directly
    result = 0
    for num in nums:
        result ^= num
    return result

    # Or using a one-liner with built-in functions
    # (though this creates intermediate values)
    result = nums[0]
    for num in nums[1:]:
        result ^= num
    return result