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)).

Additional information

• 1 <= nums.length <= 3 * 10^4
• -3 * 10^4 <= nums[i] <= 3 * 10^4
• Each element in the array appears twice except for one element which appears only once.

Example 1:

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

Explanation: 2 appears twice and 1 appears once. The single number is 1.

Example 2:

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

Explanation: 1 and 2 each appear twice, while 4 appears only once. The single number is 4.

Bitwise XOR

Intuition

The constraint of O(1) space prevents us from using a Hash Map (which would be O(n) space). We need a different approach.

The XOR Trick:
The Bitwise XOR (^) operator has two magical properties that solve this problem perfectly:

1. Identity: x ^ 0 = x (XORing with 0 keeps the number the same).
2. Self-Cancellation: x ^ x = 0 (XORing a number with itself results in 0).

Why this works:
If we XOR all the numbers in the array together, all the duplicates will cancel each other out (becoming 0), and the only thing left will be the single number.

• Example: [4, 1, 2, 1, 2]
• Calculation: 4 ^ 1 ^ 2 ^ 1 ^ 2
• Rearrange (associative property): 4 ^ (1 ^ 1) ^ (2 ^ 2)
• Simplify: 4 ^ 0 ^ 0
• Result: 4

Algorithm

Step 1: Initialize a variable result = 0.

Step 2: Iterate through every number n in nums.

Step 3: Update the result: result = result ^ n.

Step 4: Return result.

def single_number(nums: list[int]) -> int:
    result = 0
    for n in nums:
        result = result ^ n  # XOR operation
    return result

Time & Space Complexity

• Time Complexity: O(n). We iterate through the array once.
• Space Complexity: O(1). We only use one variable (result).