Watch 10 video solutions for Bulb Switcher, a medium level problem involving Math, Brainteaser. This walkthrough by The Hustling Engineer has 9,475 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There are n bulbs that are initially off. You first turn on all the bulbs, then you turn off every second bulb.
On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb.
Return the number of bulbs that are on after n rounds.
Example 1:
Input: n = 3 Output: 1 Explanation: At first, the three bulbs are [off, off, off]. After the first round, the three bulbs are [on, on, on]. After the second round, the three bulbs are [on, off, on]. After the third round, the three bulbs are [on, off, off]. So you should return 1 because there is only one bulb is on.
Example 2:
Input: n = 0 Output: 0
Example 3:
Input: n = 1 Output: 1
Constraints:
0 <= n <= 109Problem Overview: You have n bulbs initially turned off. On round 1 every bulb is toggled, on round 2 every second bulb is toggled, on round 3 every third bulb, and so on until round n. The task is to determine how many bulbs remain on after all rounds finish.
Approach 1: Counting Perfect Squares by Iteration (O(√n) time, O(1) space)
The key observation is that a bulb toggles once for every divisor of its index. For example, bulb 12 toggles on rounds 1, 2, 3, 4, 6, and 12. Most numbers have divisors in pairs such as (2,6) or (3,4), which results in an even number of toggles and the bulb ends up off. Only perfect squares have an odd number of divisors because one divisor pair collapses (e.g., 3 × 3). That means bulbs at positions 1, 4, 9, 16... stay on. Iterate i while i * i ≤ n and count how many perfect squares exist.
This approach directly models the mathematical insight without relying on built-in square root functions. It works well when you want explicit control over iteration or when implementing the logic in constrained environments. The algorithm performs about √n iterations and uses constant memory.
Approach 2: Perfect Square Insight (O(1) time, O(1) space)
The observation above leads to a simpler solution: the number of bulbs that remain on equals the number of perfect squares less than or equal to n. That value is simply ⌊√n⌋. Instead of simulating toggles, compute the integer square root of n and return it.
This converts a simulation problem into a pure math calculation. The toggle pattern becomes irrelevant once you recognize the divisor parity property of numbers. Because the algorithm performs only a single square root operation, the runtime is effectively constant with O(1) space. This is the intended optimal solution and a classic brainteaser style problem frequently seen in interviews that test pattern recognition rather than brute-force simulation.
Recommended for interviews: Interviewers expect the perfect square observation. Mentioning that bulbs toggle once per divisor demonstrates understanding of the mechanics, while deriving the ⌊√n⌋ formula shows strong problem-solving ability. Starting with the divisor reasoning and then simplifying to the math solution communicates both intuition and optimization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting Perfect Squares by Iteration | O(√n) | O(1) | When you want to explicitly count perfect squares without using built-in sqrt functions |
| Perfect Square Insight (Math) | O(1) | O(1) | Optimal interview solution using the observation that only perfect square indices remain on |