Single Number III Solutions & Complexity

1. Define the problem

Single Number III

Given an integer array nums in which exactly two elements appear only once and every other element appears exactly twice , find the two elements that appear only once. You may return the answer in any order. XOR everything together to get a XOR b, then use the lowest set bit of that XOR to split every number into two groups — a and b are guaranteed to land in different groups, so XOR-ing each group separately isolates them.

Constraints

2 ≤ nums.length ≤ 3 × 10⁴
-2³¹ ≤ nums_i ≤ 2³¹ - 1
Each integer appears twice except for two, which appear once

Example

Inputnums = [1, 2, 1, 3, 2, 5]

Output[3, 5]

Explanation 1 and 2 each appear twice and cancel out, leaving 3 and 5.

2. Know the words first

In plain terms

Lowest set bit: n & (-n) isolates the lowest bit that is 1. Since a and b differ at that bit, splitting all numbers by whether they have that bit set keeps every duplicate pair together in the same group, while a and b end up in different groups.

3. Visualize the solution

XOR everything, then split by the lowest differing bit

Statusinit

XOR every value in [1, 2, 1, 3, 2, 5] together: 1^2^1^3^2^5 = 3^5 = 6 (110).

What happens in this step

0 ^ 1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5
  0 = 00000000
  1 = 00000001
  2 = 00000010
  1 = 00000001
  3 = 00000011
  2 = 00000010
  5 = 00000101
      --------
      00000110  =  6

Every duplicate cancels itself under XOR — the two 1s cancel, the two 2s cancel — leaving only 3 XOR 5 = 6, the combined signature of the two single numbers.

Step 1 of 4

Steps to visualize

XOR every value in nums together. Every duplicate cancels, leaving xorAll = a ^ b.
Isolate the lowest set bit of xorAll with diff = xorAll & (-xorAll) — a and b differ there.
Split every number into two groups based on whether that bit is set.
XOR each group independently; each group collapses to exactly one of a or b.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

XOR everything, then split by the lowest differing bit

Statusinit

XOR every value in [1, 2, 1, 3, 2, 5] together: 1^2^1^3^2^5 = 3^5 = 6 (110).

What happens in this step

0 ^ 1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5
  0 = 00000000
  1 = 00000001
  2 = 00000010
  1 = 00000001
  3 = 00000011
  2 = 00000010
  5 = 00000101
      --------
      00000110  =  6

Every duplicate cancels itself under XOR — the two 1s cancel, the two 2s cancel — leaving only 3 XOR 5 = 6, the combined signature of the two single numbers.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function singleNumberIII(nums) {
  let xorAll = 0;

  for (const num of nums) {
    xorAll ^= num;
  }

  const diff = xorAll & -xorAll;
  let a = 0;
  let b = 0;

  for (const num of nums) {
    if (num & diff) {
      a ^= num;
    } else {
      b ^= num;
    }
  }

  return [a, b].sort((x, y) => x - y);
}

Time: O(n)
Space: O(1)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [1, 2, 1, 3, 2, 5]`	`[3, 5]`	example from the docstring
`nums = [-1, 0]`	`[-1, 0]`	smallest valid input, one negative and one non-negative value
`nums = [0, 1]`	`[0, 1]`	both values already appear once with nothing else to cancel
`nums = [4, 1, 2, 1, 2, 4, 6, 3]`	`[3, 6]`	several duplicate pairs surrounding the two single values
`nums = [1, 2]`	`[1, 2]`	boundary case with only the two single values and no pairs
`nums = [10, 20, 10, 30, 30, 40]`	`[20, 40]`	larger values spread across multiple duplicate pairs

Single Number III