LeetCode 319: Bulb Switcher

Problem Restatement

There are n bulbs in a row.

All bulbs are initially off.

We perform n rounds:

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

Input and Output

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.

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:

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

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: