Single Number

Single Number

XOR-fold the whole array — pairs cancel, the lone unmatched value remains.

Easy

Time O(n) Space O(1)

LeetCode

May 16, 2026 2 min read

Problem#

Every element appears twice except for one. Find the singleton in linear time and constant space.

Examples#

[2,2,1] → 1.
[4,1,2,1,2] → 4; [1] → 1.

Constraints#

1 <= nums.length <= 3 * 10^4, fits in 32-bit int.

Approach#

XOR every element together. Because x ^ x = 0 and x ^ 0 = x, all paired values cancel, leaving the singleton.

Solution#

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int x = 0;
        for (int v : nums) x ^= v;
        return x;
    }
};

func singleNumber(nums []int) int {
    x := 0
    for _, v := range nums {
        x ^= v
    }
    return x
}

from functools import reduce
from operator import xor
from typing import List

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(xor, nums, 0)

function singleNumber(nums) {
    let x = 0;
    for (const v of nums) x ^= v;
    return x;
}

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

function singleNumber(nums: number[]): number {
    let x = 0;
    for (const v of nums) x ^= v;
    return x;
}

Editorial#

XOR is commutative and associative, so order doesn’t matter — the unique element falls out regardless of input order. This is the canonical example of using XOR’s self-inverse property to achieve O(1) space.

Complexity#

Time: O(n).
Space: O(1).

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#