319. Bulb Switcher

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 integer x such that x^2 ≤ n, which is simply the floor of the square root of n.
• If 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)).

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));
};