100 Lockers — The Toggle Problem

Problem Statement

You're in a hallway lined with 100 closed lockers.

• Pass 1: Open every locker.
• Pass 2: Close every 2nd locker (2, 4, 6, ...).
• Pass 3: Toggle every 3rd locker (open if closed, close if open).
• ...continue for 100 passes, where on pass i you toggle every i-th locker.

After all 100 passes, how many lockers are open?

Constraints

• 100 lockers (generalize to N)
• On pass i, toggle lockers at positions i, 2i, 3i, ...

Example

Answer: 10 lockers are open (lockers 1, 4, 9, 16, 25, 36, 49, 64, 81, 100).

What the Interviewer Expects

1. Brute force first — simulate with a boolean array, toggle in nested loops. O(n²). Acknowledge it works but isn't elegant.
2. The key insight — locker k is toggled once for each divisor of k. A locker ends up OPEN if it has an odd number of divisors.
3. Only perfect squares have an odd number of divisors — because divisors pair up (e.g., 12 = 1×12, 2×6, 3×4), except perfect squares where one divisor is repeated (e.g., 16 = 1×16, 2×8, 4×4).
4. Answer = number of perfect squares ≤ N = floor(sqrt(N)). For N=100, that's 10.
5. The interviewer wants the O(1) math insight, not just the simulation.

Follow-ups

1. Generalize: for N lockers, how many are open? (Answer: floor(sqrt(N)))
2. Which specific lockers are open? (The perfect squares)
3. What if you only do the first K passes instead of all N?
4. Prove why only perfect squares have an odd number of divisors.