← Back to DSA Animator
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.