Why Do Only Perfect Squares Stay Lit? Solving the Bulb Switch Puzzle

Story Origin

Initially there are n bulbs, all in the off state. Toggling a bulb switches it on if it was off, and off if it was on.

Problem Description

In round 1 every bulb is toggled once, turning all bulbs on. In round 2 every second bulb is toggled, turning every second bulb off. In round 3 every third bulb is toggled, and so on. In round i every i ‑th bulb is toggled, and in the final round n only the last bulb is toggled.

The task is to determine how many bulbs remain on after n rounds.

Problem Analysis

Simulating each round naively would require traversing the bulbs repeatedly and is too slow for large n. Observing the toggling pattern reveals a mathematical regularity.

Discovering the Pattern

Listing the on/off states for the first ten bulbs shows that the bulbs that stay on are at positions 1, 4, 9, … – exactly the perfect squares. A perfect square has an odd number of factors, so its state is toggled an odd number of times and ends up on.

Mathematical Reasoning

For any non‑square number, factors come in pairs (e.g., 1 & 12, 2 & 6, 3 & 4 for 12), resulting in an even number of toggles and the bulb ends off. A perfect square like 9 has a middle factor (3) that pairs with itself, giving an odd count of toggles.

Thus, the number of bulbs that remain on after n rounds equals the count of perfect squares ≤ n.

Optimized Solution

The count of perfect squares up to n is simply ⌊√n⌋. Therefore the answer can be computed in O(1) time.

return (int)Math.sqrt(n);

Conclusion

In interview settings, this problem illustrates the “experiment → guess → prove” approach: observe small cases, hypothesize a pattern, and then justify it mathematically. The final solution is a one‑line computation of the integer square root of n.