Find the Single Unique Number Among Duplicates
Filed under Microsoft
Free read 3 of 3Confirm constraints regarding additional data structures or bitwise operations.
The question
Given an array where every element appears twice except for one unique element, write pseudocode or code to identify that unique number in O(n) time.
Constraints
- Linear time complexity O(N) required.
- Constant auxiliary space O(1) preferred.
Examples
- Input
- nums = [4, 1, 2, 1, 2]
- Output
- 4
- Why
- Number 4 appears only once while all other numbers appear twice.
Approach
Confirm constraints regarding additional data structures or bitwise operations.
Count frequencies of each element using a hash map or nested loops.
Use the XOR bitwise operator. XORing a number with itself cancels it out to 0 (a ^ a = 0). XORing all array elements leaves only the unique number.
Array with exactly one element.
Solution
O(N) time, O(1) space
class Solution:
def singleNumber(self, nums: list[int]) -> int:
ans = 0
for num in nums:
ans ^= num
return ans
Tips
- What they are testing: Test with a single-element array and arrays where the unique element is at the beginning or end.
- Common mistake: Using a hash map, which satisfies O(N) time but violates the optimal O(1) space constraint.
Related Microsoft questions
Collected from public candidate posts and coding forums. Updated Nov 2026.