Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

• Difficulty: MEDIUM
• Problem: Bulb Switcher
• Topics: Math, Brainteaser

Problem gist

There are n bulbs, all initially off. The process runs for n rounds. On round 1, every bulb is toggled; on round 2, every second bulb is toggled; on round 3, every third bulb is toggled; and so on. The goal is to count how many bulbs remain on after the final round.

A direct simulation works, but it repeats a great deal of unnecessary work. The important question is not what happens during each round, but how many times a particular bulb is toggled in total.

Deriving the optimal solution

Number the bulbs from 1 through n. Bulb k is toggled on exactly the rounds whose numbers divide k. For example, bulb 12 is toggled on rounds 1, 2, 3, 4, 6, and 12 because those are the divisors of 12.

A bulb starts off, so it ends on only when it is toggled an odd number of times. Divisors normally arrive in pairs: if d divides k, then k / d is also a divisor. For 12, the pairs are (1, 12), (2, 6), and (3, 4), giving an even divisor count.

The only time a divisor is paired with itself is when k is a perfect square. Bulb 9, for example, has divisor pairs (1, 9) and (3, 3); the repeated square root contributes only one distinct divisor, so the total number of divisors is odd. Therefore exactly the perfect-square-numbered bulbs remain on.

The answer is simply the number of perfect squares no greater than n: 1², 2², ..., floor(sqrt(n))². That count is floor(sqrt(n)). Python’s math.isqrt computes this value exactly with integer arithmetic, avoiding floating-point rounding at square boundaries.

Under the usual fixed-width integer model, the solution takes O(1) time and O(1) extra space. More importantly, it avoids the O(n log n) work of toggling every affected bulb in every round.

Python solution

from math import isqrt


class Solution:
    """Count bulbs that remain on after the complete toggle process."""

    def bulbSwitch(self, number_of_bulbs: int) -> int:
        """Return the number of lit bulbs after all rounds.

        A bulb remains on exactly when its one-based position is a perfect
        square. Thus the answer is the integer square root of the bulb count.
        """
        if number_of_bulbs < 0:
            raise ValueError("number_of_bulbs must be non-negative")

        # isqrt returns floor(sqrt(number_of_bulbs)) without float rounding.
        return isqrt(number_of_bulbs)

Interview follow-ups

Why does every non-square have an even number of divisors?

Each divisor d of a number k can be paired with the distinct divisor k / d. These pairs account for every divisor, so their total count is even. The two values can be equal only when d² = k, which means k is a perfect square. A square has one unpaired divisor—its square root—and therefore an odd divisor count. Since toggling an off bulb an odd number of times leaves it on, this proves that only square-numbered bulbs survive.

How would the solution return the positions of all bulbs that remain on?

Generate 1², 2², ..., floor(sqrt(n))². The same proof identifies these as exactly the lit positions, and no search or simulation is necessary. Generating them takes O(sqrt(n)) time and O(sqrt(n)) space for the returned list. That time and space are optimal up to constants because the output itself contains floor(sqrt(n)) positions.

What changes if every bulb starts on instead of off?

An even number of toggles would leave a bulb on, while an odd number would turn it off. Perfect-square positions are still the only positions toggled an odd number of times, so those bulbs end off and every non-square ends on. The answer becomes n - floor(sqrt(n)), with the same O(1) time and space under the fixed-width model.

What if there are only m rounds for n bulbs, where m < n?

Bulb k would then be toggled only by divisors of k that are at most m. The clean divisor-pair argument no longer determines the parity because one member of a pair may correspond to a round greater than m. A straightforward solution keeps a Boolean state for every bulb and toggles multiples of each round number from 1 through m. It takes O(n/1 + n/2 + ... + n/m) = O(n log m) time and O(n) space. The tradeoff illustrates why completing all n rounds is the special condition that makes the square-root shortcut possible.

How can the answer be found without a square-root function?

Binary-search for the largest integer candidate whose square is at most n. To avoid multiplication overflow in a fixed-width language, compare candidate <= n / candidate using integer division, treating zero separately. The search takes O(log n) time and O(1) space. It is slower than a built-in integer square root but relies only on basic arithmetic and preserves exactness.

Why prefer an integer square root over converting sqrt(n) to an integer?

Floating-point numbers cannot represent every sufficiently large integer exactly. Near a perfect-square boundary, rounding can make a floating-point square root land just below or above the correct integer, producing an off-by-one result after conversion. An integer square-root routine guarantees the exact floor for arbitrary supported integer values. Its bit-level cost matters for enormous integers, but for ordinary interview constraints it retains the intended constant-space, no-simulation solution.