Single Number

Approach Summary

XOR all numbers. Pairs cancel out (x ^ x = 0). The result is the single number.

Full Solution & Approach

XOR has three properties that make this a one-liner: a ^ a = 0, a ^ 0 = a, and XOR is commutative and associative. Since every number except one appears exactly twice, XORing the entire array cancels every duplicate pair to 0 and leaves only the singleton. Order does not matter because XOR is commutative, so a single pass with result = 0 and result ^= n for each n works regardless of arrangement. This is the canonical linear-time, constant-space solution, and the trick is worth remembering — the same XOR idea generalizes to finding the missing number and the two odd-occurring numbers. Any non-bitwise approach (hash map, sort, or sum) either uses O(n) extra space or O(n log n) time.

One pass with a constant-time XOR per element — O(n) time. A single integer variable — O(1) space.

Solution Code

Solution

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

function singleNumber(nums) {
  return nums.reduce((acc, n) => acc ^ n, 0);
}

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

int singleNumber(const vector<int>& nums) {
    int result = 0;
    for (int n : nums) result ^= n;
    return result;
}

Edge Cases to Watch

Single element — the singleton itself
Negative numbers — XOR works identically on two's-complement integers
Large arrays — no overflow risk with XOR, unlike sum-based tricks

How to Recognize This Pattern

Find element appearing once, all others twice
XOR trick

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)