Given an array containing n distinct numbers taken from the range 0 to n, find the one number in the range that is missing from the array.
For example, given [3, 0, 1], the missing number is 2. Given [9,6,4,2,3,5,7,0,1], the missing number is 8.
Explain multiple approaches and their tradeoffs. Then describe how to solve this using bit manipulation in O(n) time and O(1) space, and explain why it works.
How to approach it
- Hint 1
The sum formula approach: the sum of 0 to n is n*(n+1)/2. Subtract the array sum to find the missing number. What is the risk with this approach?
- Hint 2
For the XOR approach, think about XORing every index with every value. If an index i has value i, they cancel.
- Hint 3
XOR indices 0 through n with all array values -- every number appears twice except the missing one.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.