LeetCode 319 - Bulb Switcher

LeetCode Problem 319

Difficulty: 🟡 Medium
Topics: Math, Brainteaser

Solution

Problem Understanding

The problem describes a sequence of n bulbs, all initially turned off. We perform n rounds of operations on these bulbs. In the first round, every bulb is turned on. In the second round, every second bulb is toggled, meaning on bulbs become off and off bulbs become on. In the third round, every third bulb is toggled, and so on until the nth round, where only the last bulb is toggled.

The goal is to determine how many bulbs remain on after all n rounds are completed.

The input is a single integer n, representing both the number of bulbs and the number of rounds. The output is a single integer, representing the count of bulbs that are still on at the end.

The constraint 0 <= n <= 10^9 is extremely important. A value this large immediately tells us that simulating every bulb and every toggle operation directly is not practical. Any solution with time complexity near O(n^2) or even O(n log n) would be too slow for the upper bound. This strongly suggests that the problem has a mathematical observation or pattern that leads to a constant-time or logarithmic-time solution.

Several edge cases are important:

• When n = 0, there are no bulbs at all, so the answer must be 0.
• When n = 1, the only bulb is turned on once and never toggled again, so the answer is 1.
• Large values such as 10^9 require an efficient mathematical solution because brute-force simulation would be infeasible.
• Perfect squares behave differently from other numbers, which becomes the key insight for the optimal approach.

Approaches

Brute Force Approach

The most direct way to solve this problem is to simulate the process exactly as described.

We can create an array of n boolean values representing the bulbs. Initially, all bulbs are False, meaning off. For each round i, we toggle every ith bulb. After all rounds are completed, we count how many bulbs remain on.

This approach is correct because it follows the problem statement exactly. Every bulb is updated according to the required rounds and toggling rules.

However, the performance is very poor. In the worst case, we perform roughly:

n + n/2 + n/3 + ... + n/n

operations, which is approximately O(n log n) toggles. With n as large as 10^9, this is impossible to run within time limits. The memory usage is also large because we must explicitly store all bulb states.

Key Mathematical Insight

Instead of simulating toggles, we should ask a different question:

How many times is a particular bulb toggled?

Consider bulb number k. It is toggled once for every divisor of k.

For example, bulb 12 is toggled during rounds:

1, 2, 3, 4, 6, 12

because those are the divisors of 12.

A bulb ends up:

• On if it is toggled an odd number of times
• Off if it is toggled an even number of times

Most numbers have divisors that come in pairs.

For example:

12:
(1, 12)
(2, 6)
(3, 4)

This gives an even number of divisors.

But perfect squares are different.

For example:

9:
(1, 9)
(3, 3)

The square root only appears once, not as a distinct pair. Therefore, perfect squares have an odd number of divisors.

That means:

• Only bulbs at perfect square positions remain on
• The answer is simply the number of perfect squares less than or equal to n

The number of perfect squares less than or equal to n is:

$\lfloor\sqrt{n}\rfloor$

So the entire problem reduces to computing the integer square root of n.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(n)	Simulates every toggle operation directly
Optimal	O(1)	O(1)	Counts perfect squares using integer square root

Algorithm Walkthrough

1. Observe that bulb k is toggled once for every divisor of k.
2. Recall that divisors usually appear in pairs. For example, if 2 divides 12, then 6 also divides 12.
3. Because divisor pairs contribute two toggles, most bulbs are toggled an even number of times and end up off.
4. Perfect squares are the exception because their square root divisor is repeated. For example, 16 has divisor pair (4,4) instead of two distinct divisors.
5. Therefore, perfect squares have an odd number of divisors and remain on after all rounds.
6. Count how many perfect squares exist between 1 and n.
7. The largest perfect square less than or equal to n is determined by the integer square root of n.
8. Return floor(sqrt(n)).

Why it works

A bulb's final state depends entirely on how many divisors its index has. Numbers with an even number of divisors are toggled an even number of times and become off. Numbers with an odd number of divisors are toggled an odd number of times and remain on. Only perfect squares have an odd number of divisors because one divisor pair collapses into a single repeated divisor at the square root. Therefore, the number of bulbs left on equals the number of perfect squares less than or equal to n.

Python Solution

import math

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

The implementation is intentionally very small because the mathematical observation eliminates the need for simulation.

The math.isqrt() function computes the integer square root of n, meaning the greatest integer whose square is less than or equal to n.

For example:

• isqrt(9) returns 3
• isqrt(10) also returns 3

This directly corresponds to the number of perfect squares less than or equal to n.

The conversion to int is technically unnecessary because isqrt() already returns an integer, but it makes the intent explicit and keeps the return type clear.

Go Solution

package main

import "math"

func bulbSwitch(n int) int {
	return int(math.Sqrt(float64(n)))
}

The Go implementation uses math.Sqrt, which operates on float64 values. Therefore, we first convert n to float64, compute the square root, and then convert the result back to int.

Because the problem only requires the integer floor of the square root, truncating the floating-point result via int() gives the correct answer.

Unlike Python's math.isqrt, Go does not provide a dedicated integer square root function in the standard library, so this conversion approach is standard practice.

Worked Examples

Example 1

Input: n = 3

We examine bulbs 1 through 3.

Bulb	Divisors	Number of Toggles	Final State
1	1	1	On
2	1, 2	2	Off
3	1, 3	2	Off

Now count perfect squares less than or equal to 3.

Perfect Square	Value
1²	1

There is only one perfect square.

Answer = 1

Example 2

Input: n = 0

There are no bulbs.

No perfect squares exist less than or equal to 0.

Perfect Squares ≤ 0	Count
None	0

Answer = 0

Example 3

Input: n = 1

Bulb 1 is toggled once.

Bulb	Divisors	Number of Toggles	Final State
1	1	1	On

Perfect squares less than or equal to 1:

Perfect Square	Value
1²	1

Answer = 1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only computes the integer square root
Space	O(1)	Uses no extra data structures

The optimal solution does not simulate any bulb operations. It relies entirely on the mathematical property of divisor counts. Computing the integer square root is effectively constant time for the problem constraints and requires only a few variables.

Test Cases

solution = Solution()

assert solution.bulbSwitch(0) == 0  # No bulbs
assert solution.bulbSwitch(1) == 1  # Single bulb remains on
assert solution.bulbSwitch(2) == 1  # Only bulb 1 remains on
assert solution.bulbSwitch(3) == 1  # Example case
assert solution.bulbSwitch(4) == 2  # Perfect squares: 1, 4
assert solution.bulbSwitch(5) == 2  # Perfect squares: 1, 4
assert solution.bulbSwitch(8) == 2  # Perfect squares: 1, 4
assert solution.bulbSwitch(9) == 3  # Perfect squares: 1, 4, 9
assert solution.bulbSwitch(10) == 3  # Still only 3 perfect squares
assert solution.bulbSwitch(15) == 3  # Perfect squares: 1, 4, 9
assert solution.bulbSwitch(16) == 4  # Perfect squares: 1, 4, 9, 16
assert solution.bulbSwitch(24) == 4  # Largest perfect square <= 24 is 16
assert solution.bulbSwitch(25) == 5  # Perfect squares: 1, 4, 9, 16, 25
assert solution.bulbSwitch(100) == 10  # Squares from 1^2 to 10^2
assert solution.bulbSwitch(10**9) == 31622  # Large constraint boundary

Test	Why
n = 0	Validates empty input handling
n = 1	Smallest non-zero case
n = 2	Confirms non-square bulbs turn off
n = 3	Matches provided example
n = 4	First case with multiple perfect squares
n = 9	Verifies perfect square counting
n = 10	Confirms floor square root behavior
n = 16	Tests another perfect square boundary
n = 25	Larger perfect square validation
n = 10^9	Stress test for maximum constraint

Edge Cases

One important edge case is n = 0. A naive implementation might assume there is at least one bulb and accidentally access invalid indices or return 1 incorrectly. The mathematical solution handles this naturally because sqrt(0) = 0.

Another critical edge case is when n itself is a perfect square, such as 16 or 25. These values are important because the count should include the square itself. Using the integer floor of the square root correctly includes these cases. For example, floor(sqrt(25)) = 5, which counts 1, 4, 9, 16, 25.

A third important edge case involves numbers just below a perfect square, such as 15 or 24. These cases verify that the algorithm correctly floors the square root rather than rounding it. For example, sqrt(15) is approximately 3.87, but only the perfect squares 1, 4, 9 are valid, so the answer must be 3.

Large values such as 10^9 are also essential edge cases because they expose the inefficiency of simulation-based solutions. The mathematical approach remains efficient because it performs only a square root computation regardless of input size.