The 100 Doors Problem
The Puzzle: You have 100 closed doors.
- You walk past and open every door.
- Every 2nd door, you toggle it (if open, close it; if closed, open it).
- Every 3rd door, you toggle it. … and so on until the 100th pass. Which doors are open at the end?
1. The Logic
Think about a single door, say Door #12. When is it toggled?
- On pass 1, 2, 3, 4, 6, and 12. These are the factors of 12.
- Since 12 has 6 factors (an even number), it will be toggled 6 times.
- Closed -> Open -> Closed -> Open -> Closed -> Open -> Closed.
2. The Pattern
A door stays OPEN only if it is toggled an odd number of times.
- When does a number have an odd number of factors?
- Only when it is a Perfect Square (e.g., 9: 1, 3, 9).
3. The Result
The open doors are: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.
Interview-Focused Questions
Q: Why do perfect squares have an odd number of factors?
A: Normally, factors come in pairs (e.g., for 12: 1x12, 2x6, 3x4). But for a perfect square like 16, one pair is the same number (4x4). This “single” factor makes the total count odd.
Q: If there were 1000 doors, how many would be open?
A: Find the largest n such that n2≤1000. Since 312=961 and 322=1024, exactly 31 doors would be open.
Complexity Note
This puzzle is often used to see if you can solve a problem using Number Theory instead of brute-force simulation.
Premium Content
Unlock 100 Doors Puzzle and all premium lessons with a subscription.
All premium lessons
Ad-free experience
Priority support
From ₹199.99/year — See plans