Single Number
Maintained by Vikas D, software engineer
You receive an array of integers in which all but one value show up exactly twice. The remaining value appears a single time. Your job is to identify and return that lone value.
The array is never empty, and the duplicated values can sit anywhere relative to one another, in any order. There is always exactly one value without a partner.
The interesting part is the resource budget. A counting map would work but costs extra memory proportional to the input. The expectation here is a pass that runs in linear time while holding only a fixed amount of extra state, regardless of how large the array grows.
Examples
Two appears twice and cancels out, so 1 is the only value left standing alone.
The two 1s pair off and the two 2s pair off, leaving 4 as the unmatched value even though it sits at the front.
Negative values pair just like positive ones, so the two -1s cancel and 9 remains.
Constraints
- 1 <= nums.length <= 3 * 10^4
- -3 * 10^4 <= nums[i] <= 3 * 10^4
- Every value appears exactly twice except for one value that appears once.
- Target solution runs in O(n) time and O(1) extra space.
Visible test cases
- singleNumber([2,2,1]) == 1
- singleNumber([4,1,2,1,2]) == 4
- singleNumber([1]) == 1
- singleNumber([3,3,7,7,5]) == 5
- singleNumber([-1,-1,9]) == 9
Hints
Hint 1
A hash map that counts how many times each value appears would solve it, but think about whether you can avoid storing all those counts.
Hint 2
Pairs of equal values should somehow neutralize each other, so the operation you fold over the array needs that cancelling behavior.
Hint 3
XOR has two useful properties: any value XOR itself is 0, and any value XOR 0 is unchanged. Fold XOR across the whole array and the pairs vanish.
Approaches
Hash map counting
Time O(n) · Space O(n)Tally how often each value occurs, then return the one with a count of one.
- Walk the array once, incrementing a count for each value in a map.
- Walk the map (or the array again) and return the value whose count equals one.
XOR fold (optimal)
Time O(n) · Space O(1)XOR is associative and commutative, a value XOR itself is 0, and a value XOR 0 is itself, so XORing every element together cancels all the pairs and leaves only the lone value.
- Start an accumulator at 0.
- XOR each element of the array into the accumulator in turn.
- Every paired value cancels to 0, so the accumulator ends holding the single unpaired value.
- Return the accumulator.
Common mistakes
- Reaching for a Set or hash map and accepting the O(n) extra space, which misses the constant-space requirement the prompt sets.
- Sorting the array first and scanning for the odd one out, which adds an O(n log n) factor and may also mutate the caller's input.
- Initializing the XOR accumulator to the first element but then also XORing that first element again in the loop, which double-counts it. Start at 0 and fold every element once.
- Assuming the single value cannot be negative. XOR handles negative integers correctly, so no special case is needed.
Follow-up variations
- What if every value appears three times except one that appears once? XOR no longer cancels cleanly, so you count bits per position modulo three.
- What if exactly two values appear once and the rest appear twice? You XOR everything, then split into two groups using a set bit of the combined result.
- Could you return the answer without any extra accumulator variable, for example by reducing in place?
- How would the bit-counting variant change if the integers were unbounded big integers rather than fixed-width?