
Description
You have n
bulbs that are initially turned off. You first turn on every bulb. Then, you toggle every second bulb (turning it off if it's on, and turning it on if it's off). On the third round, you toggle every third bulb, and so on. This process continues for n
rounds. The task is to determine how many bulbs are on after n
rounds.
Intuition
A bulb ends up being toggled in rounds that are factors of its position. For example, bulb 12 is toggled in rounds 1, 2, 3, 4, 6, and 12. A bulb remains on if it is toggled an odd number of times, which only happens for bulbs at positions that are perfect squares (because only perfect squares have an odd number of divisors). Therefore, the number of bulbs that remain on is equal to the number of perfect squares less than or equal to n
.
Approach
- The number of bulbs that remain on is the number of perfect squares ≤
n
. This is equivalent to finding the largest integerx
such thatx^2 ≤ n
, which is simply the floor of the square root ofn
. - If
n = 0
, no bulbs are on. Ifn = 1
, only 1 bulb remains on. For any other value ofn
, the result is the largest integerx
such thatx^2
≤n
, which can be computed usingfloor(sqrt(n))
.
Complexity
Time Complexity:
- The time complexity is (O(1)) because calculating the square root of
n
and flooring it is a constant-time operation.
Space Complexity:
- The space complexity is (O(1)) because no extra space is used apart from a few variables for calculation.
Code
C++
class Solution {
public:
int bulbSwitch(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return (int)sqrt(n);
}
};
Python
class Solution:
def bulbSwitch(self, n: int) -> int:
if n == 0:
return 0
if n == 1:
return 1
return math.floor(math.sqrt(n))
Java
class Solution {
public int bulbSwitch(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return (int) Math.floor(Math.sqrt(n));
}
}
JavaScript
var bulbSwitch = function (n) {
if (n === 0) return 0;
if (n === 1) return 1;
return Math.floor(Math.sqrt(n));
};