Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Cancel equal pairs: The XOR Observatory.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when XOR cancellation matches the clues
- 2Keep this true after every move: the accumulator equals the XOR of every processed value
- 3Reach the result within O(n)
Rules and pressure
- Target cost: O(n)
- State rule: the accumulator equals the XOR of every processed value
Lesson 1 of 3
Live algorithm trace
XOR cancellation
Complete execution1 of 7
Start with XOR's neutral value, zero.
1
answer = 02
for value in nums3
answer ^= value4
return answeranswer = 0
Truth to preserve / Cost target
Truth to preserve
the accumulator equals the XOR of every processed value
Cost target
O(n)
XOR cancels equal values because x XOR x is zero, and zero XOR x is x. Pair duplicates in any order and the unpaired value remains.
Your call · What should guide every step of this algorithm?