The Puzzle: You have an Excel sheet containing numbers from 1 to 100 in a single column, but they are shuffled. One number is missing. How do you find it?
1. Finding One Missing Number
The most efficient way is using the Sum Formula.
- Expected Sum: Calculate the sum of numbers from 1 to 100:
- Sum = n(n + 1) / 2 = (100 × 101) / 2 = 5050.
- Actual Sum: Sum all the numbers currently in your sheet.
- Result: Missing Number = Expected Sum - Actual Sum.
2. Finding Two Missing Numbers
This is much harder. If you only use the sum, you get the value of (X + Y). You need another equation.
- Calculate Sum of Squares: Sum of squares = n(n + 1)(2n + 1) / 6.
- Calculate the actual sum of squares of the numbers you have.
- The difference gives you X² + Y².
- With X+Y and X² + Y², you can solve for X and Y using basic algebra.
Interview-Focused Questions
Q: How would you solve this without using math sums (to prevent overflow)?
A: Use the XOR operator. XOR all numbers from 1 to 100, then XOR that result with all the numbers in your sheet. The remaining value will be the missing number. This is safe from “Integer Overflow” which could happen with large sums.
Q: What is the time and space complexity?
A: Time: O(N) (single pass over the data). Space: O(1) (you only store a single sum or XOR result).
Key Takeaway
This puzzle is frequently used as a warm-up for Array/Hash Table questions. It tests your ability to optimize space (O(1) instead of using a Set).
Premium Content
Unlock Missing Number and all premium lessons with a subscription.
From ₹199.99/year — See plans