Skip to main content
Ace Hired
All coding problems

Single Number

Easyarrays hashingBit manipulation (XOR)arraybit-manipulationxor

Maintained by Vikas D, software engineer

You receive a non-empty list of integers. The list is built so that each number is paired with an identical copy somewhere else in the list, with one single exception: exactly one number has no partner.

Your job is to find and return that unpaired number. The array is not sorted, the values can be negative or zero, and the lone number may sit anywhere in the list.

The interesting constraint is efficiency. A correct answer is easy, but the version interviewers look for runs in one pass over the array and uses only a fixed amount of extra memory regardless of input size.

Examples

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

The two 2s cancel as a pair, so 1 is the value left without a match.

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

The pair of 1s and the pair of 2s each cancel out, leaving 4 as the only unpaired number.

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

Negative values behave the same way: the two -1s pair off and -2 is the single number.

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4
  • Every element appears exactly twice except for one element that appears once.
  • Target solution runs in linear time and uses constant extra space.

Visible test cases

  • singleNumber([2,2,1]) == 1
  • singleNumber([4,1,2,1,2]) == 4
  • singleNumber([1]) == 1
  • singleNumber([0,1,0]) == 1
  • singleNumber([-1,-1,-2]) == -2

Hints

Hint 1

A pair of equal numbers contributes nothing if you can find an operation where combining a value with itself produces a neutral result.

Hint 2

Bitwise XOR has two properties that matter here: x XOR x is 0, and x XOR 0 is x. Order does not matter either.

Hint 3

Fold the whole array together with XOR starting from 0. Everything that appears twice cancels to 0, so only the lone value survives.

Loading the editor...

Approaches

Hash map count

Time O(n) · Space O(n)

Count how many times each value occurs, then return the one with an odd count.

  1. Walk the array and tally each value in a hash map.
  2. Walk the map and return the key whose count is 1.
  3. This also works as a set you toggle: add a value on first sight, remove it on second sight, and whatever remains is the answer.

Optimal XOR fold

Time O(n) · Space O(1)

XOR cancels equal pairs to zero, so XOR-ing every element together leaves only the unpaired one.

  1. Start an accumulator at 0.
  2. XOR each element of the array into the accumulator.
  3. Because x XOR x is 0 and x XOR 0 is x, all paired values cancel and the accumulator ends holding the single number.
  4. Return the accumulator.

Common mistakes

  • Reaching for a hash map or set when the problem explicitly wants constant extra space; the XOR fold is the intended answer.
  • Forgetting that XOR handles negative numbers and zero correctly, so no special casing is needed for them.
  • Initializing the XOR accumulator to something other than 0, which corrupts the result.
  • Assuming the array is sorted and trying to compare adjacent pairs; the input order is arbitrary.

Follow-up variations

  • What if every element appears three times except one that appears once? XOR no longer cancels cleanly, so you count bits per position modulo 3.
  • What if exactly two elements appear once and the rest appear twice? XOR everything, then use a set bit of that result to split the array into two groups.
  • Can you return the single number without ever materializing the full array, processing it as a stream?

Recommended problems

Build the rest of your prep