Single Number

Problem in Plain English

Find the one element that appears exactly once in an array where every other element appears twice. The answer must come from a single linear pass using only constant extra space.

Problem Statement

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

The solution must run in linear time and use only constant extra space, which rules out sorting the array or counting frequencies with a hash map.

Constraints

$1 \le \text{nums.length} \le 3 \times 10^4$
$-3 \times 10^4 \le \text{nums}[i] \le 3 \times 10^4$
Every element appears twice except one element that appears once.

Examples

Example 1

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

The value 2 appears twice and cancels out, leaving 1 as the single number.

Example 2

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

Both 1 and 2 appear twice, so the unpaired value 4 is the answer.

Example 3

Input: nums = [1]
Output: 1

With only one element, it is trivially the single number.

Example 4

Input: nums = [-2, 0, -2, 3, 3]
Output: 0

The separated negative pair -2 cancels, as does the pair 3. Zero occurs once, so returning 0 is a real answer rather than evidence that no value was found.

Intuition

Think of each duplicate as a pair that should disappear. In [2, 2, 1], removing the two copies of 2 leaves 1. A set can remember which values still need a partner, but XOR performs the same cancellation directly on bits: equal bits XOR to zero, and zero XOR a bit keeps that bit. Because XOR can be regrouped, the two copies need not be adjacent.

Approaches

Hash Set Tracking

Solution Details

Reveal Hash Set Tracking: intuition, complexity, and code

Intuition

Add each number on first sight and erase it on second sight, so the set always holds values seen an odd number of times. Pairing by hand is intuitive but the set can grow with the input.

Step-by-Step Logic

Start with an empty set and read 2, which is absent, so add it.
Read the next 2, which is present, so remove it and leave the set empty.
Read 1, which is absent, so add it.
The scan is done and the set holds exactly one value.
Return the remaining value 1.

Why It Works

After each prefix, the set contains exactly the values appearing an odd number of times in that prefix: a first occurrence adds a value and a second removes it. At the end every paired value has been removed, and the guaranteed single value remains. Returning that one entry is therefore correct. This is a useful baseline, but it does not meet the required constant extra space.

Dry Run

Hash Set Tracking: variable states at each step
value	action	set after
`2`	add	`{2}`
`2`	remove	`{}`
`1`	add	`{1}`
done	return lone entry	`1`

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

Let n be the array length. Set membership, insertion and removal take expected constant time, yielding expected O(n) time. If all first copies arrive before their partners, the set contains (n + 1)/2 entries and uses O(n) auxiliary space, including Java boxed integers and hash storage. The iterator and scalar result are constant size. The input is never mutated.

Code

Solution.java

1import java.util.HashSet;2import java.util.Set;3
4class Solution {5    public int singleNumber(int[] nums) {6        // Membership records odd occurrence counts in the scanned prefix.7        Set<Integer> seen = new HashSet<>();8        for (int num : nums) {9            if (seen.contains(num)) {10                seen.remove(num);11            } else {12                seen.add(num);13            }14        }15        return seen.iterator().next();16    }17}

Hints

Hint 1

Pairing each value with its twin suggests a set: add on first sight, remove on second sight.

Hint 2

The set version works but stores up to half the array, breaking the constant-space demand.

Hint 3

Recall that a ^ a is 0 and a ^ 0 is a, so xoring the whole array leaves only the unpaired value.

Edge Cases

A one-element array returns that element with no pairing work.
Negative values cancel correctly because xor acts on the raw two's complement bits.
The single element may sit at either end, so no position assumption is safe.

Common Mistakes and Interview Tips

Counting frequencies with a map, which meets the time bound but breaks the constant-space rule.
Sorting first and scanning for the break, which costs $O(n log n)$ time instead of linear time.
Returning the set object itself instead of extracting its lone entry.
Using an accumulator initialized to the first value and then scanning the entire array, which counts that first value twice.
Applying this exact XOR fold when repeated values occur three times; pair cancellation relies on the stated multiplicities.

Key Takeaway

When pairs cancel, look for an operation that is its own inverse: folding the input with xor erases duplicates without storing them.