Single Number
Asked at Meta
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Meta | EASY | View all Meta questions → |
How to Think About It
Hash map: count frequency of each element, return the one with count 1 — O(n) time but O(n) space.
Sorting: sort the array and scan for the unpaired element — O(n log n) time, O(1) space.
Set sum trick: 2 * sum(set) - sum(array) equals the single number — clever but uses O(n) space.
Bit manipulation insight: XOR of a number with itself is 0, XOR of 0 with a number is the number.
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.
What Trips People Up in Real Interviews
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.
Solution Code
def single_number(nums):
result = 0
for num in nums:
result ^= num
return resultFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.