Bulb Switcher
MedPrompt
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: 0Example 3:
Input: n = 1
Output: 1
Constraints:
0 <= n <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to simulate the entire process. We create an array of n bulbs and toggle each bulb according to the rules for each round.
Algorithm
- Create a boolean array of size n to represent bulbs (initially all false/off)
- For each round i from 1 to n:
- Toggle every i-th bulb (starting from position i-1)
- Count the number of bulbs that are true (on)
- Return the count
Walkthrough
We simulate the entire bulb switching process by maintaining an array to track the state of each bulb. For each round i (from 1 to n), we toggle every i-th bulb. After all rounds, we count how many bulbs remain on.
public int bulbSwitch(int n) { if (n == 0) return 0; boolean[] bulbs = new boolean[n]; // Simulate each round for (int round = 1; round <= n; round++) { // Toggle every round-th bulb for (int i = round - 1; i < n; i += round) { bulbs[i] = !bulbs[i]; } } // Count bulbs that are on int count = 0; for (boolean bulb : bulbs) { if (bulb) count++; } return count;}This approach directly implements the problem description. In round 1, we toggle all bulbs (turning them on). In round 2, we toggle every 2nd bulb. This continues until round n where we only toggle the n-th bulb.
Complexity
Time
O(n × n/1 + n × n/2 + ... + n × 1) ≈ O(n²) - For each round i, we toggle n/i bulbs, and the sum of n/i for i from 1 to n is approximately n × log(n), but the nested loops make it O(n²)
Space
O(n) - We need an array of size n to store the state of each bulb
Trade-offs
Pros
Easy to understand and implement
Directly follows the problem description
Good for understanding the problem pattern
Cons
Very inefficient for large values of n
Will cause Time Limit Exceeded for n up to 10^9
Uses significant memory for large n
Instead of simulating the entire process, we can count how many times each bulb gets toggled. A bulb that is toggled an odd number of times will be on.
Algorithm
- Initialize count to 0
- For each bulb position i from 1 to n:
- Count the number of divisors of i
- If the count is odd, increment the result count
- Return the count
Walkthrough
Rather than maintaining the state of each bulb through all rounds, we can observe that a bulb's final state depends only on how many times it gets toggled. Since all bulbs start off, a bulb will be on if and only if it's toggled an odd number of times.
public int bulbSwitch(int n) { int count = 0; // For each bulb position for (int i = 1; i <= n; i++) { int toggleCount = 0; // Count how many rounds toggle this bulb for (int round = 1; round <= i; round++) { if (i % round == 0) { toggleCount++; } } // If toggled odd number of times, it's on if (toggleCount % 2 == 1) { count++; } } return count;}Bulb i is toggled in round j if and only if j divides i evenly. So we count the divisors of each bulb position. If the count is odd, the bulb is on.
Complexity
Time
O(n²) - For each of n bulbs, we check up to n potential divisors
Space
O(1) - We only use a few variables regardless of input size
Trade-offs
Pros
No need to maintain bulb states
More efficient than simulation
Reveals the mathematical pattern
Cons
Still too slow for large n
Doesn't leverage the mathematical insight fully
The key insight is that a bulb will be on if and only if it has an odd number of divisors. Only perfect squares have an odd number of divisors.
Algorithm
- Calculate the square root of n
- Return the floor of the square root
Walkthrough
The crucial observation is that bulb i is toggled once for each divisor of i. For most numbers, divisors come in pairs (d, i/d). However, perfect squares have an unpaired divisor (the square root), giving them an odd number of divisors.
public int bulbSwitch(int n) { return (int) Math.sqrt(n);}Why does this work?
- Bulb i is toggled in round j if j divides i
- The number of times bulb i is toggled equals the number of divisors of i
- Most numbers have an even number of divisors (they come in pairs: if d divides n, then n/d also divides n)
- Perfect squares have an odd number of divisors because the square root pairs with itself
- Example: 16 has divisors {1, 2, 4, 8, 16}, but we can pair them as (1,16), (2,8), and 4 pairs with itself
- Therefore, only bulbs at perfect square positions (1, 4, 9, 16, ...) will be on
- The number of perfect squares ≤ n is floor(√n)
Complexity
Time
O(1) - Computing square root is considered constant time
Space
O(1) - Only uses a single variable
Trade-offs
Pros
Extremely efficient - constant time
Elegant mathematical solution
Works for any value of n within constraints
No memory overhead
Cons
Requires mathematical insight to understand
Not immediately obvious from problem description
Solutions
Solution
class Solution {public int bulbSwitch(int n) { return (int)Math.sqrt(n); }}class Solution {public: int bulbSwitch(int n) { return (int)sqrt(n); }};class Solution: def bulbSwitch(self, n: int) -> int: return int(n ** (1 / 2))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.