← Microsoft questions

Find the Single Unique Number Among Duplicates

Filed under Microsoft

Free read 3 of 3

Confirm 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

  1. Confirm constraints regarding additional data structures or bitwise operations.

Solution

O(N) time, O(1) space

Python
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.