Problem statement

Given a non-empty array nums where every element appears twice except for one, find that single one.

Your solution should run in linear time and use only constant extra space.

Example 1

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

Example 2

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

Constraints

• 1 <= nums.length <= 29 (odd)
• -100 <= nums[i] <= 100
• Every element appears twice except one.

Hints for Single Number

1. Hint 1

   x XOR x = 0, and XOR is order-independent.

2. Hint 2

   XOR the whole array together — the pairs cancel and the single survives.

How to solve Single Number

XOR is its own inverse: x ^ x == 0, and x ^ 0 == x. XOR the entire array together and every value that appears twice cancels itself out, leaving exactly the one that does not.

Approach

1. Start with an accumulator of 0.
2. XOR every element into it.
3. Return the accumulator.

Why it works

XOR is associative and commutative, so the array can be reordered freely without changing the result — which means the pairs can be imagined side by side, each collapsing to 0. What survives is the unpaired value XOR-ed with a pile of zeros, which is the value itself. That is why no bookkeeping is needed: the cancellation is done by the operator, giving linear time and constant space where a hash set would cost O(n) memory.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Seed the accumulator at 0, the identity for XOR — seeding with nums[0] also works but only if the loop then starts at index 1.
• This works only because every other value appears exactly twice; three occurrences would break the cancellation.
• Negative values are fine — XOR operates on the bit patterns.
• A hash set gives the right answer but violates the constant-space requirement.

Reference solution

Python

from typing import List

def singleNumber(nums: List[int]) -> int:
    acc = 0
    for x in nums:
        acc ^= x
    return acc

Java

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

C++

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

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy