Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Cancel indices against values: The Missing Orbit.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Missing number XOR matches the clues
- 2Keep this true after every move: the accumulator is the XOR difference between processed indices and values
- 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: the accumulator is the XOR difference between processed indices and values
Lesson 1 of 3
Live algorithm trace
Missing number XOR
Complete execution1 of 5
Seed answer with range endpoint 3.
1
answer = array length2
for each index and value3
answer XOR= index4
answer XOR= value5
return answerrange = 0..3answer = 3
Truth to preserve / Cost target
Truth to preserve
the accumulator is the XOR difference between processed indices and values
Cost target
O(n) time and O(1) space
XOR every complete-range index and every present value. All shared numbers cancel, leaving the one range member absent from the array.
Your call · What should guide every step of this algorithm?