Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Split two unique values by one differing bit: The Twin Outliers.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Single Number III matches the clues
- 2Keep this true after every move: each duplicate enters one bucket twice and cancels, while the uniques enter opposite buckets
- 3Reach the result within O(n) time and O(1) space
Rules and pressure
- Target cost: O(n) time and O(1) space
- State rule: each duplicate enters one bucket twice and cancels, while the uniques enter opposite buckets
Lesson 1 of 3
Live algorithm trace
Single Number III
Complete execution1 of 5
XOR the full array so all paired values cancel.
1
combined = XOR of all values2
mask = combined & -combined3
left = right = 04
partition values by mask bit5
XOR within each bucket6
return the two bucket resultscombined = 3 XOR 5 = 6binary = 110
Truth to preserve / Cost target
Truth to preserve
each duplicate enters one bucket twice and cancels, while the uniques enter opposite buckets
Cost target
O(n) time and O(1) space
XOR cancels every pair, leaving uniqueA XOR uniqueB. Any set bit in that result separates the two uniques into different XOR buckets.
Your call · What should guide every step of this algorithm?