Skip to content
Optimal Lab

Math & Bits · 046Easy

Single Number

Given a non-empty array where every element appears twice except for one, find that single element. Must run in O(n) time using O(1) extra space.

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4
  • Every element appears twice except one.
  • You must use only constant extra space.

Examples

singleNumber([2, 2, 1])        ->  1
singleNumber([4, 1, 2, 1, 2])  ->  4
singleNumber([1])              ->  1
singleNumber([0, 1, 1])        ->  0    // the loner may be 0
singleNumber([-1, -1, 3])      ->  3    // negatives pair off too
singleNumber([5, -3, 5])       ->  -3   // the loner may be negative

Edge cases

  • A single-element array.
  • Negative numbers.
Show the target complexity (spoiler)
Naive
O(n) time but O(n) space — count occurrences in a map.
Target
O(n) time, O(1) space — XOR every element: pairs cancel to 0 and the loner survives.

Solve it

By hand, in your editor. The runner checks answers and timing.

git clone https://github.com/sarmadkung/optimal-round
cd optimal-round
# open problems/12-math-bits/046-single-number.js
./practice c 046
Open the file on GitHub ↗