Dare2Solve
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.
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
.
n
. This is equivalent to finding the largest integer x
such that x^2 ≤ n
, which is simply the floor of the square root of n
.n = 0
, no bulbs are on. If n = 1
, only 1 bulb remains on. For any other value of n
, the result is the largest integer x
such that x^2
≤ n
, which can be computed using floor(sqrt(n))
.n
and flooring it is a constant-time operation.class Solution {
public:
int bulbSwitch(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return (int)sqrt(n);
}
};
class Solution:
def bulbSwitch(self, n: int) -> int:
if n == 0:
return 0
if n == 1:
return 1
return math.floor(math.sqrt(n))
class Solution {
public int bulbSwitch(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return (int) Math.floor(Math.sqrt(n));
}
}
var bulbSwitch = function (n) {
if (n === 0) return 0;
if (n === 1) return 1;
return Math.floor(Math.sqrt(n));
};