Skip to main content

136. Single Number

easy

Every element in the array appears twice except one. Find the singleton in O(n) time and O(1) space. The canonical XOR trick — the gateway problem to bit manipulation.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. You must implement a solution with a linear runtime complexity and use only constant extra space.

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4
  • Each element in the array appears twice except for one element which appears only once.

Examples

Example 1

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

Example 2

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

Example 3

Input
nums = [1]
Output
1

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

A hash map gives O(n) time but O(n) space — the constraints want O(1) space.

Hint 2

Think about a binary operator with two useful properties: x ^ x == 0 and x ^ 0 == x.

Hint 3

XOR is commutative and associative. If you XOR every element together, paired values cancel out and the singleton remains.

Solution approach

Reveal approach

Initialize result = 0. Iterate through nums and XOR each element into result. Because XOR is commutative and associative, and because a ^ a == 0 and a ^ 0 == a, every duplicated pair cancels itself out regardless of order. After the loop, result holds the value that appeared once. O(n) time, O(1) space — and one of the few problems where the optimal solution is literally a single line of code.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • bit-manipulation
  • xor

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft
  • Apple
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Single Number and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →