DSA AnimatorDSA animations
Single Number III LC #260 Medium XOR Partition
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. Return the answer in any order.

Example 1
Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation: 3 and 5 each appear once; 1 and 2 appear twice.
Example 2
Input: nums = [3,7,3,4]
Output: [7,4]
Explanation: 7 and 4 appear once; 3 appears twice.
Constraints: 2 ≤ nums.length ≤ 3·10⁴  |  Each integer appears exactly twice except for two integers which appear once
Try Examples
Custom:
Approach
XOR Partition — Two-Phase Algorithm
Phase 1: XOR all → get a^b. Phase 2: find lowest differing bit, partition array into two groups each containing one unique + its duplicates, XOR each group.
Input Array
XOR Accumulator
xorAll
0
binary
00000000
Step Logic
Press ▶ Play or Next Step to begin.
✅
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
XOR all → xor = a^b (pairs cancel to 0)
2
xor & (-xor) isolates the lowest differing bit between a and b
3
Partition: bit set → group A, bit clear → group B
4
XOR each group → each gives one unique number
Time
O(n)
Space
O(1)
Why It Works

All pairs XOR to 0, leaving xor=a^b. Since a≠b, at least one bit differs. We pick the lowest such bit. It splits the array so one group has a (and a's pairs) and the other has b (and b's pairs). XOR within each group cancels the pairs, leaving the unique number.

How to solve Single Number III

LeetCode 260 · Medium · Bit Manipulation · Pattern: XOR + Split by Bit

Why the obvious approach is slow

A hash set works, but uses extra space. Plain XOR of everything gives 3 XOR 5, not the two numbers themselves.

The key idea

XOR everything, and the pairs cancel, leaving x equal to a XOR b. Because a and b are different, x has at least one 1 bit, where a and b differ. Take the lowest set bit of x, using x AND minus x. Split the numbers into two groups by that bit, so a and b land in different groups. Pairs stay together, so XOR each group to get a and b.

Remember

One differing bit separates the two singles. x AND minus x isolates the lowest set bit.

Run the animation above on your own input, or watch the 1:37 video explanation of Single Number III with a dry run and Java code.

More Bit Manipulation problems