Skip to main content

260. Single Number III

medium

Exactly two elements appear once; every other element appears twice. Find both singletons in O(n) time and O(1) space. The XOR-and-split trick.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order. You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

Constraints

  • 2 <= nums.length <= 3 * 10^4
  • -2^31 <= nums[i] <= 2^31 - 1
  • Each integer in nums will appear twice, only two integers will appear once.

Examples

Example 1

Input
nums = [1,2,1,3,2,5]
Output
[3,5]

Explanation: [5, 3] is also a valid answer.

Example 2

Input
nums = [-1,0]
Output
[-1,0]

Example 3

Input
nums = [0,1]
Output
[1,0]

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

XOR all numbers — the result is a ^ b where a and b are the two singletons. The pairs cancel.

Hint 2

a != b, so a ^ b has at least one set bit. Pick any set bit — say the lowest, computed with xor & -xor.

Hint 3

That bit is set in exactly one of a or b. Partition nums into two groups by whether that bit is set, then XOR each group separately.

Solution approach

Reveal approach

Compute xor_all = XOR of every element; this equals a ^ b. Isolate the lowest set bit: mask = xor_all & -xor_all (works because in two's complement -x flips all bits above the lowest set bit then adds 1). Walk the array a second time, splitting elements into two buckets by whether (num & mask) is nonzero. XOR each bucket separately — duplicate pairs still cancel within each bucket because identical elements land in the same bucket. The two surviving XOR values are a and b. O(n) time, O(1) space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • bit-manipulation
  • xor

Related problems

Asked at

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

  • Amazon
  • Google
  • Microsoft
  • Apple

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →