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 Sam K., 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

More Math practice problems

See all Math problems →