Bulb Switcher
Medium · Math & Geometry · Explanation and code example
Count Perfect Squares
How it works
Bulb k is toggled once per positive divisor of k. Divisors usually come in pairs, leaving an even number of toggles. Only perfect squares have an unpaired square-root divisor, so exactly the square-numbered bulbs remain on.
Steps
- Recognize that only squares have an odd divisor count.
- Compute floor(sqrt(n)).
- Return that count.
Complexity
- Time: O(1) in the fixed-width integer model.
- Space: O(1).
Things to watch for
- Use an integer square root in Python.
- For n = 0, there are no bulbs.
- A square at the upper boundary must be included.
Python code example
import math
class Solution:
def bulbSwitch(self, n: int) -> int:
# The k-th bulb can only be switched when k % i == 0.
# So, we can rephrase the problem:
# To find number of numbers <= n that have odd factors.
# Obviously, only square numbers have odd factor(s).
# e.g. n = 10, only 1, 4, and 9 are square numbers that <= 10
return math.isqrt(n)
C++ code example
class Solution {
public:
int bulbSwitch(int n) {
// The k-th bulb can only be switched when k % i == 0.
// So, we can rephrase the problem:
// To find number of numbers <= n that have odd factors.
// Obviously, only square numbers have odd factor(s).
// e.g. n = 10, only 1, 4, and 9 are square numbers that <= 10
return sqrt(n);
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.