Scale Engineer

Bulb Switcher

Med
#0306Time: 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 bulb1 company
Patterns
Math
Companies
Accenture

Prompt

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 <= 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

  1. Create a boolean array of size n to represent bulbs (initially all false/off)
  2. For each round i from 1 to n:
    • Toggle every i-th bulb (starting from position i-1)
  3. Count the number of bulbs that are true (on)
  4. 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

Solutions

class Solution {public  int bulbSwitch(int n) { return (int)Math.sqrt(n); }}

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.

← Previous

Previous problem

Next →

Next problem