Problem Description

The Bulb Switcher problem asks: Given n bulbs that are initially off, you perform n rounds of toggling bulbs. In the i-th round, every bulb that is a multiple of i (1-indexed) is toggled (on to off or off to on). After all rounds, return the number of bulbs that remain on.

• Each bulb is toggled in rounds corresponding to its divisors.
• Constraints: 1 <= n <= 109
• Only one valid answer exists for each n.
• Do not simulate the toggling process directly for large n due to performance constraints.

Thought Process

At first glance, it may seem natural to simulate the toggling process for each bulb and each round. However, with constraints up to 10⁹, brute-force is not practical. Instead, we seek a mathematical pattern or shortcut.

Let's consider toggling: A bulb at position k is toggled every time i divides k. Thus, the number of times a bulb is toggled is equal to the number of divisors of its position number. If a bulb is toggled an odd number of times, it ends up on; if even, it ends up off.

But which numbers have an odd number of divisors? Only perfect squares! For example, 9 has divisors 1, 3, 9. All other numbers have pairs of divisors. Therefore, only bulbs at perfect square positions remain on.

Solution Approach

To solve the problem efficiently, we use the insight that only bulbs at perfect square positions are on at the end.

• Step 1: Count how many perfect squares are less than or equal to n. This is the same as finding the largest integer k such that k * k ≤ n.
• Step 2: The answer is simply floor(sqrt(n)).
• Why this works: Because only positions 1, 4, 9, 16, ..., k² (where k² ≤ n) have an odd number of divisors, and thus are toggled an odd number of times.
• Implementation: Use the square root function from the language's standard library and return its integer part.

Example Walkthrough

Example Input: n = 10

• Bulb positions: 1 to 10
• Perfect squares ≤ 10: 1 (1²), 4 (2²), 9 (3²)
• So, bulbs at positions 1, 4, and 9 will be on.
• Counting: There are 3 perfect squares ≤ 10.
• Result: 3 bulbs remain on

Step-by-step:

1. Find sqrt(10) ≈ 3.16
2. Floor of sqrt(10) is 3
3. Return 3

Time and Space Complexity

• Brute-force approach:
  • Time: O(n √n) or worse, since we'd simulate each round for each bulb.
  • Space: O(n), to store bulb states.
• Optimized approach:
  • Time: O(1), since we only compute the integer square root.
  • Space: O(1), no extra storage needed.
• Why? The mathematical insight reduces the problem to a single calculation.

Code Implementation

import math

class Solution:
    def bulbSwitch(self, n: int) -> int:
        return int(math.isqrt(n))
      

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

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

var bulbSwitch = function(n) {
    return Math.floor(Math.sqrt(n));
};
      

Summary

The Bulb Switcher problem is a classic example of how mathematical insight can drastically simplify a problem. By recognizing that only bulbs at perfect square positions are toggled an odd number of times, we reduce the problem to counting perfect squares ≤ n. This allows for a constant-time and space solution, making it both elegant and efficient.