In an array where every element appears twice except for one, finding that unique element is a classic coding interview challenge. While you could use a hash map, bitwise XOR provides an O(1) space solution.

Problem Statement

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

Example

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

Output: 4

Explanation: All numbers appear twice except for 4.

The XOR Property

XOR (^) has specific properties that make it perfect for this:

• Self-Cancellation: x ^ x = 0. A number XORed with itself becomes zero.
• Identity: x ^ 0 = x. XORing any number with zero keeps the number unchanged.
• Commutative: Order doesn't matter (a ^ b ^ a is the same as a ^ a ^ b).

Python Implementation

def find_single_number(nums):
    result = 0
    for n in nums:
        result ^= n
    return result

# Test
print(find_single_number([4, 1, 2, 1, 2])) # Output: 4

Complexity

• Time Complexity: O(N) - We traverse the array once.
• Space Complexity: O(1) - We only use one variable to store the result.