Single Number easy

Description

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

Solve it in O(n) time and O(1) extra space.

Examples

> Case 1:
    Input:  nums = [2, 2, 1]
    Output: 1
 
> Case 2:
    Input:  nums = [4, 1, 2, 1, 2]
    Output: 4
 
> Case 3:
    Input:  nums = [1]
    Output: 1

Constraints

• 1 <= nums.length <= 3 * 10^4
• -3 * 10^4 <= nums[i] <= 3 * 10^4
• Each integer appears twice, except for one integer which appears once.

Why a hash set is the wrong answer

The obvious solution — count each number with a hash map, return the one with count 1 — works in O(n) time, but it uses O(n) extra space. The problem explicitly asks for O(1) space, which rules out any auxiliary data structure that grows with the input.

We need something cleverer.

The XOR insight

Recall the three magic XOR identities from the intro:

• x ^ 0 = x
• x ^ x = 0
• XOR is commutative and associative — order doesn’t matter.

Put them together. If we XOR every element of nums, every pair (x, x) cancels to 0, and we’re left with the single x ^ 0 = x.

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

4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)     # reorder freely
= 4 ^ 0 ^ 0
= 4

That’s it. No hash map, no sort, no extra storage — just one running XOR.

Code

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

def single_number(nums):
    result = 0
    for x in nums:
        result ^= x
    return result
 
# one-liner version
from functools import reduce
from operator import xor
def single_number_fp(nums):
    return reduce(xor, nums)

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

Four lines. No fancy data structures. Works for any number of pairs in any order — XOR doesn’t care.

Analysis

• Time: O(n) — one pass.
• Space: O(1) — a single accumulator.

Bonus: what if every element appears three times except one?

XOR doesn’t cancel triples — x ^ x ^ x = x, not 0. The classic solution uses two accumulators (ones and twos) tracking bits seen once and bits seen twice mod 3:

def single_number_ii(nums):
    ones = twos = 0
    for x in nums:
        ones = (ones ^ x) & ~twos
        twos = (twos ^ x) & ~ones
    return ones

That’s Single Number II on LeetCode — same XOR family, harder version of the same trick. The idea is identical: design a state machine that’s invariant under triples but transforms once for the singleton.