EasyArrayBit ManipulationUpdated Sep 2026

136. Single Number

Asked at Meta

Difficulty

Easy

Time

O(n)

Space

O(1)

Pattern

Array

Companies

1

Problem

You get an array of integers. Every value in the array shows up exactly twice, except for one value that shows up exactly once. Return that lonely value.

The array is never empty, so there is always an answer. The catch is the limits on your solution: it must run in linear time and use constant extra space. That rules out the easy tricks of counting with a hash map (too much memory) or sorting the array (too slow).

The intended trick is XOR. XOR has two useful properties: a value XORed with itself gives 0, and a value XORed with 0 gives back the value. So if you XOR every element together, all the pairs cancel out to 0 and only the single value is left.

Pairs cancel, one value is left

nums221012Orange cells are the matching pair; the green cell isthe single number.
In [2,2,1] the two 2s form a pair and the 1 has no partner, so the answer is 1.

Constraints

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

Examples

Example 1
Inputnums = [2,2,1]
Output1
WhyThe two 2s cancel each other out, so only 1 remains.
Example 2
Inputnums = [4,1,2,1,2]
Output4
Why1 and 2 each appear twice and cancel, leaving 4.
Example 3
Inputnums = [1]
Output1
WhyThere is only one element, so it is the single number.

Asked At

1 companies
CompanyDifficulty
MetaEasyView all Meta questions →

How to Think About It

1

Hash map: count frequency of each element, return the one with count 1 — O(n) time but O(n) space.

2

Sorting: sort the array and scan for the unpaired element — O(n log n) time, O(1) space.

3

Set sum trick: 2 * sum(set) - sum(array) equals the single number — clever but uses O(n) space.

4

Bit manipulation insight: XOR of a number with itself is 0, XOR of 0 with a number is the number.

5

Optimal: XOR all elements together — duplicates cancel out and the single number remains — O(n) time, O(1) space.

Optimal Approach

XOR all elements in the array together. Since every number that appears twice XORs to zero (a ^ a = 0), and XOR is commutative and associative, the running XOR accumulator will hold only the value that appeared an odd number of times — the single number. This runs in O(n) time with O(1) space.

XOR everything together

nums221012iStart with result = 0 and walk the array left toright.result = 0 ^ 2 = 2result = 2 ^ 2 = 0result = 0 ^ 1 = 1The pair cancels to 0, then the leftover 1 becomes theanswer.a ^ a = 0a ^ 0 = aanswer = 2 ^ 2 ^ 1 = 1
Each pair XORs to 0, and 0 XOR the single value gives that value back.
ComplexityTime O(n)Space O(1)We scan the array once and keep a single accumulator variable, so the cost is one pass over n elements.

What Trips People Up in Real Interviews

1

Ask whether the array always contains exactly one single number or could have multiple.

2

Confirm that O(n) time and O(1) space are the target constraints.

3

Explain why XOR works before coding — interviewer wants to see you reason about bit operations.

4

Mention that this extends to finding single numbers that appear once while others appear k times.

5

Edge case: array of length 1 — the single element is trivially the answer.

Solution Code

O(n) time
def single_number(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Single Number problem?

Given a non-empty array of integers where every element appears twice except for one, find that single element. Your solution should have linear time complexity and use constant extra space, ruling out hash map or sorting approaches.

How do you solve Single Number?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Single Number?

Single Number is asked at Meta. It is a easy difficulty problem.

What are common mistakes on Single Number?
  • Ask whether the array always contains exactly one single number or could have multiple.
  • Confirm that O(n) time and O(1) space are the target constraints.
  • Explain why XOR works before coding — interviewer wants to see you reason about bit operations.
  • Mention that this extends to finding single numbers that appear once while others appear k times.
  • Edge case: array of length 1 — the single element is trivially the answer.