Bulb Switcher: Why Only Perfect Squares Stay On

319. Bulb Switcher sets up a deceptively simple scenario: you have n bulbs, all initially off. In round i (for i from 1 to n), you toggle every bulb whose position is divisible by i. After all n rounds, how many bulbs are on?

For example, with n=3, only bulb 1 stays on, giving an answer of 1. With n=6, bulbs 1 and 4 stay on, giving an answer of 2.

The key is figuring out which bulbs end up on, and then counting them efficiently.

The insight: divisors determine the final state

Think about a single bulb at position k. It gets toggled in round i if and only if i divides k. So the total number of times bulb k gets toggled equals the number of divisors of k.

A bulb starts off. It ends up on if and only if it was toggled an odd number of times. So the question becomes: for which values of k does k have an odd number of divisors?

Here is where the pairing argument comes in. Divisors naturally come in pairs: if d divides k, then k/d also divides k, and d and k/d are a pair. Most numbers have all their divisors neatly paired up, giving an even total.

The exception is when d equals k/d, which means d * d = k. This happens exactly when k is a perfect square. In that case, the square root of k is its own pair, and it contributes just one divisor instead of two. The total divisor count is odd.

So bulb k is on after n rounds if and only if k is a perfect square.

That means you just need to count how many perfect squares exist from 1 to n. Those are 1, 4, 9, 16, 25, ... up to n. The largest perfect square that fits is floor(sqrt(n))^2, so the count is floor(sqrt(n)).

import math

def bulbSwitch(n: int) -> int:
    return int(math.isqrt(n))

Walking through n=6

Let's verify with n=6:

• Bulb 1: divisors [1], 1 toggle, ON
• Bulb 2: divisors [1, 2], 2 toggles, OFF
• Bulb 3: divisors [1, 3], 2 toggles, OFF
• Bulb 4: divisors [1, 2, 4], 3 toggles, ON
• Bulb 5: divisors [1, 5], 2 toggles, OFF
• Bulb 6: divisors [1, 2, 3, 6], 4 toggles, OFF

Two bulbs are on. And floor(sqrt(6)) = 2. It checks out.

Complexity

The entire solution is a single call to isqrt. There are no loops, no arrays, no recursion. Python's math.isqrt uses integer arithmetic and runs in constant time for practical input sizes.

The building blocks

Divisor pairing argument. Divisors of any integer k come in pairs (d, k/d). This pairing is symmetric, so the total count is even unless one divisor equals its own pair, meaning d = sqrt(k). That only happens when k is a perfect square. This argument appears in number theory frequently, and recognizing it unlocks a whole class of problems.

Integer square root. math.isqrt(n) gives floor(sqrt(n)) using integer arithmetic, avoiding floating-point rounding errors that could trip you up for large n. For example, math.sqrt(999999999999999999) may not return exactly 999999999 due to float precision, but math.isqrt handles it correctly.

Counting perfect squares. The pattern of "count perfect squares up to n" shows up in surprising places, including range queries, grid problems, and combinatorial counting. Any time a problem reduces to "how many integers from 1 to n satisfy some property that filters down to perfect squares," the answer is isqrt(n).

Edge cases

• n=0: isqrt(0) = 0. No bulbs exist, so 0 are on. Correct.
• n=1: isqrt(1) = 1. Bulb 1 is toggled once in round 1 and stays on. Correct.
• Large n: Python's math.isqrt is designed for arbitrarily large integers and handles inputs up to and beyond 64-bit range without loss of precision.

From understanding to recall

The fact to lock in is: divisors come in pairs, and perfect squares break the pairing. Once you see that, the rest follows automatically. You do not need to remember any formula. Just reason from "each toggle corresponds to a divisor" to "odd toggles means odd divisor count" to "odd divisor count means perfect square" to "count = isqrt(n)."

In an interview, the mental chain is fast: divisors pair up, square roots are their own pair, count the squares. That is the whole problem.

Related posts

• Count Primes - Another math problem where the key is reasoning about which numbers have special divisibility properties
• Nim Game - A game theory problem that also reduces to a one-line formula once you find the right pattern
• Happy Number - Number theory meets cycle detection, another problem that looks complex but has a clean closed-form structure