#319

Medium

LeetCode Problem Workspace

Bulb Switcher

Bulb Switcher challenges you to find how many bulbs remain on after n toggling rounds using a math-based insight.

Problem Statement

You are given n bulbs arranged in a line, all initially off. You perform n rounds of toggling: in round i, you toggle every ith bulb. The first round turns all bulbs on, the second toggles every second bulb, and this pattern continues until the nth round, which only toggles the last bulb.

Return the total number of bulbs that are on after completing all n rounds. For example, with n = 3, after three rounds only the first bulb remains on, so the output is 1.

Examples

Example 1

Input: n = 3

Output: 1

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 details omitted.

Example 3

Input: n = 1

Output: 1

Example details omitted.

Constraints

0 <= n <= 109

Solution Approach

Mathematical Insight

Observe that a bulb changes state once for each factor it has. Bulbs with an odd number of factors remain on, which occurs only for perfect squares. This eliminates the need for step-by-step simulation.

Direct Computation

Compute the integer part of the square root of n. This count corresponds exactly to the number of bulbs that remain on. For instance, n = 9 results in 3 bulbs on because 1, 4, and 9 are perfect squares.

Avoid Simulation

Simulating all rounds for large n is inefficient. Recognizing the perfect square pattern reduces time and space complexity to O(1) for both, allowing immediate calculation for any n up to 10^9.

Complexity Analysis

Metric	Value
Time	O(1)
Space	O(1)

Time complexity is O(1) because only the integer square root calculation is needed. Space complexity is O(1) as no additional storage is required for tracking bulb states.

What Interviewers Usually Probe

Expect candidates to identify the divisor pattern instead of iterating through rounds.
Look for recognition that only perfect squares have an odd number of factors.
Candidates may attempt simulation first, signaling partial understanding of the toggle logic.

Common Pitfalls or Variants

Common pitfalls

Simulating each round leads to timeouts for large n values.
Failing to connect bulb toggles with number of divisors results in incorrect counting.
Misinterpreting the pattern and counting all bulbs rather than just perfect squares.

Follow-up variants

Modify the problem to count bulbs off after n rounds instead of on, still relying on perfect square logic.
Introduce multiple toggle sequences with different step sizes to test mathematical generalization.
Consider circular bulb arrangements where toggles wrap around, requiring adjusted divisor logic.

FAQ

What is the fastest way to solve Bulb Switcher without simulating rounds?

Compute the integer square root of n. Each perfect square bulb remains on, so this count gives the correct answer instantly.

Why do only perfect square bulbs stay on in Bulb Switcher?

Bulbs toggle once for each factor. Non-square numbers have factors in pairs, resulting in an even toggle count (off), while perfect squares have an odd count (on).

Can I simulate each toggle round for Bulb Switcher?

Simulation works for small n, but it is inefficient and will fail for large n due to time complexity. Using the perfect square method is recommended.

Does the solution change for very large n?

No. The solution remains O(1) and uses integer square root calculation, handling n up to 10^9 efficiently.

Is this problem primarily math or algorithm focused?

Bulb Switcher combines Math and Brainteaser patterns, requiring insight into divisors and toggle behavior rather than traditional algorithmic loops.

terminal

Solution

Solution 1: Mathematics

We can number the $n$ bulbs as $1, 2, 3, \cdots, n$. For the $i$-th bulb, it will be operated in the $d$-th round if and only if $d$ is a factor of $i$.

1

2

3

class Solution:
    def bulbSwitch(self, n: int) -> int:
        return int(sqrt(n))

Continue Practicing

#292 nim game #810 chalkboard xor game #1025 divisor game