LeetCode 319: Bulb Switcher

Problem Restatement

There are n bulbs in a row.

All bulbs are initially off.

We perform n rounds:

Round	Operation
1	Turn on every bulb
2	Toggle every second bulb
3	Toggle every third bulb
i	Toggle every ith bulb
n	Toggle only the nth bulb

Return how many bulbs are on after all rounds. The official constraints are 0 <= n <= 10^9.

Input and Output

Item	Meaning
Input	Integer n
Output	Number of bulbs left on
Initial state	All bulbs are off
Action	Toggle means off becomes on, and on becomes off

Function shape:

def bulbSwitch(n: int) -> int:
    ...

Examples

Example 1:

n = 3

Initial state:

off off off

After round 1:

on on on

After round 2:

on off on

After round 3:

on off off

Only one bulb is on.

Output:

1

Example 2:

n = 0

There are no bulbs.

Output:

0

Example 3:

n = 1

There is one bulb.

Round 1 turns it on.

Output:

1

First Thought: Simulate the Rounds

We can create an array of n booleans.

Then for each round i, toggle every multiple of i.

bulbs = [False] * n

for step in range(1, n + 1):
    for pos in range(step, n + 1, step):
        bulbs[pos - 1] = not bulbs[pos - 1]

This is correct for small n.

But n can be as large as 10^9, so simulation is impossible.

We need to understand the final state directly.

Key Insight

Look at one bulb.

Bulb k is toggled once for every round number that divides k.

For example, bulb 12 is toggled in rounds:

1, 2, 3, 4, 6, 12

because those are exactly the divisors of 12.

So the final state of bulb k depends on the number of divisors of k.

Number of toggles	Final state
Even	Off
Odd	On

Since every bulb starts off, only bulbs toggled an odd number of times remain on.

Why Perfect Squares Matter

Most divisors come in pairs.

For example, for 12:

1 * 12
2 * 6
3 * 4

That gives an even number of divisors.

But for a perfect square, one divisor pairs with itself.

For example, for 16:

1 * 16
2 * 8
4 * 4

The divisor 4 is counted only once.

So 16 has an odd number of divisors:

1, 2, 4, 8, 16

Therefore:

Bulb position	Final state
Perfect square	On
Not a perfect square	Off

So the answer is the number of perfect squares less than or equal to n.

Counting Perfect Squares

The perfect squares up to n are:

1^2, 2^2, 3^2, ..., k^2

where:

k * k <= n

The largest such k is:

floor(sqrt(n))

So the answer is:

floor(sqrt(n))

Algorithm

1. Compute the integer square root of n.
2. Return it.

In Python, use:

math.isqrt(n)

This returns the exact integer floor of the square root.

Correctness

Bulb k is toggled exactly once for each divisor of k.

A bulb remains on exactly when it is toggled an odd number of times.

Every non-square integer has divisors that pair as (a, k / a), so it has an even number of divisors.

Every perfect square has one unpaired divisor, its square root, so it has an odd number of divisors.

Therefore, exactly the bulbs at perfect-square positions remain on.

The number of perfect squares from 1 through n is floor(sqrt(n)).

So returning math.isqrt(n) gives exactly the number of bulbs left on.

Complexity

Metric	Value	Why
Time	O(1)	Integer square root is constant for fixed-size input constraints
Space	O(1)	No extra data structure is needed

Implementation

import math

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

Code Explanation

The whole problem reduces to counting perfect squares.

math.isqrt(n)

returns the largest integer x such that:

x * x <= n

That is exactly the number of perfect squares up to n.

Testing

def run_tests():
    s = Solution()

    assert s.bulbSwitch(0) == 0
    assert s.bulbSwitch(1) == 1
    assert s.bulbSwitch(2) == 1
    assert s.bulbSwitch(3) == 1
    assert s.bulbSwitch(4) == 2
    assert s.bulbSwitch(10) == 3
    assert s.bulbSwitch(16) == 4
    assert s.bulbSwitch(999999999) == 31622
    assert s.bulbSwitch(1000000000) == 31622

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
0	No bulbs
1	First perfect square
2, 3	Only bulb 1 remains on
4	Bulbs 1 and 4 remain on
10	Perfect squares are 1, 4, 9
16	Includes 4^2
Large inputs	Confirms no simulation