AlgoViz
HomeBit Manipulation

Single Number - III

Medium

Split the array on one differing bit

Problem

Exactly two elements appear once and all others appear twice. Find both single numbers.

In simple words

XOR all to get a^b, use any differing bit to split numbers into two groups, then XOR each group.

The idea

XORing everything leaves a ^ b, the XOR of the two unique values. Any set bit in that result is a position where a and b differ, so partitioning the array on that bit puts them in separate groups — and XORing each group gives one of them.

The trick

  • Isolate a differing bit with `xor & -xor`.
  • Every duplicate pair lands in the same group, so it still cancels.
  • O(n) time, O(1) space.
4
1
2
1
2
0
1
2
3
4
acc0

Step 1 of 7. XOR has a magic property: a ^ a = 0 and a ^ 0 = a. So pairs cancel and the loner survives. Values: 4, 1, 2, 1, 2. acc 0.

1/7
Optimal
timeO(n)spaceO(1)

Fold with ^.

1// XOR everything; identical values cancel2let acc = 0;3for (const x of nums)4  acc ^= x;5return acc;

Input

array
[4, 1, 2, 1, 2]

Memory

i
—
acc
0

Output

acc
0
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [1, 2, 1, 3, 2, 5]
Output:
[3, 5]
Explanation:
3 and 5 are the two lonely numbers.

Example 2

Input:
nums = [1, 1, 4, 6]
Output:
[4, 6]
Explanation:
4 and 6 appear once.

Example 3

Input:
nums = [7, 9]
Output:
[7, 9]
Explanation:
Both 7 and 9 are unpaired.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.