Skip to main content

136. Single Number

easy

Find the unique integer that appears once in an array where every other integer appears twice. The textbook XOR-magic problem — a one-line solution in O(n) time and O(1) extra space.

By Alex Chen, 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

Hash map approach (O(n) time, O(n) space) violates the constant-space requirement.

Hint 2

Math: sum can help — 2 * (sum of unique) - sum(nums) = the unique. But the duplication can overflow for adversarial inputs and requires a hash set anyway.

Hint 3

Key identity: a XOR a = 0 and 0 XOR b = b. XOR is commutative and associative.

Hint 4

So XOR all the numbers together; every pair cancels, and the single number survives.

Solution approach

Reveal approach

XOR every element together. Because a XOR a = 0 and XOR is commutative/associative, every duplicated pair cancels, leaving only the unique number. Initialize result = 0; for each num in nums, result ^= num; return result. O(n) time, O(1) extra space. The clean three-line answer is the canonical interview response. Alternative if XOR is forbidden: hash set — add on first sight, remove on duplicate; the only remaining element is the answer. O(n) time and space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • bit-manipulation
  • math

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Apple
  • Bloomberg
  • Adobe

Practice these live with InterviewChamp.AI

Drill Single Number and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →