Single Number

Problem

You are given a non-empty array nums in which every element appears exactly twice except for one element, which appears exactly once. Return that single element. You must do it in linear time using only constant extra space.

Examples

• [2, 2, 1] → 1. The two 2s pair up; 1 is unpaired.
• [4, 1, 2, 1, 2] → 4. The 1s and 2s each pair up; 4 is unpaired.
• [7] → 7. A single element with no pair.

Constraints

• 1 <= len(nums) <= 3 * 10^4
• -3 * 10^4 <= nums[i] <= 3 * 10^4
• Every element appears twice except one, which appears once.

Required: O(n) time and O(1) extra space.

Think about it first

TL;DR

XOR the whole array. Paired values cancel and the unpaired value remains. O(n) time, O(1) space.

Approach 1 — Brute force: hash set (or counter)

Track what you have seen. Toggle each value in a set: add it on first sight, remove it on second. Only the unpaired value is left at the end.

def singleNumber(nums: list[int]) -> int:
    seen = set()
    for num in nums:
        if num in seen:
            seen.remove(num)
        else:
            seen.add(num)
    return seen.pop()

Complexity: O(n) time, O(n) space for the set.

This meets the time bound but violates the O(1) space requirement: in the worst case the set holds about n/2 elements. XOR removes the extra space entirely.

Approach 2 — XOR fold

XOR is self-inverse (x ^ x = 0) and is commutative and associative, so the order in which you combine values does not matter. Fold every element together with XOR: each value that appears twice cancels against its duplicate somewhere in the fold, regardless of where the duplicates sit in the array. The one value without a pair is XORed only with the accumulated 0, and x ^ 0 = x, so it remains as the final result. One variable, one pass, no extra space.

At the bit level, XOR compares the two operands bit by bit and outputs 1 only where the bits differ. Two copies of the same number agree in every bit, so they XOR to all zeros. That is why pairs cancel.

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

Walkthrough on [4, 1, 2, 1, 2] (result starts at 0):

Returns 4. Reordering the array as [1, 1, 2, 2, 4] shows why: (1^1) ^ (2^2) ^ 4 = 0 ^ 0 ^ 4 = 4.

Complexity: O(n) time, O(1) space — one accumulator.

A one-liner using the same fold:

from functools import reduce
from operator import xor

def singleNumber(nums: list[int]) -> int:
    return reduce(xor, nums, 0)

Common pitfalls

• Seeding with the wrong identity: start the accumulator at 0 (XOR’s identity). Seeding with nums[0] works only if you then skip that element, which is easy to get wrong.
• Reaching for sum tricks: 2 * sum(set(nums)) - sum(nums) gives the same answer but uses O(n) space for the set, no better than the hash approach.
• Assuming “twice” means adjacent: duplicates can appear anywhere. XOR’s order-independence is what makes their position irrelevant.
• Generalizing carelessly: this XOR fold works only when the odd one out appears once and every other value appears an even number of times. “Every other element appears three times” (Single Number II) needs a different bit-counting scheme.

Pattern takeaway

XOR is the standard tool for finding the unpaired element: folding a collection with XOR cancels every value that appears an even number of times and leaves the odd one out. With the two identities x ^ x = 0 and x ^ 0 = x, plus order-independence, a class of “find the single or different value” problems reduces to one pass and one variable.