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 Sam K., 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

More Bit Manipulation practice problems

See all Bit Manipulation problems →