319. Bulb Switcher – Leetcode Solutions

Example 1:

Input: n = 3
Output: 1
Explanation: At first, the three bulbs are [off, off, off].
After the first round, the three bulbs are [on, on, on].
After the second round, the three bulbs are [on, off, on].
After the third round, the three bulbs are [on, off, off]. 
So you should return 1 because there is only one bulb is on.

Example 2:

Input: n = 0
Output: 0

Example 3:

Input: n = 1
Output: 1

class Solution:
    def bulbSwitch(self, n: int) -> int:
        # The number of bulbs that remain on is the count of perfect squares <= n.
        # This is equivalent to the integer part of the square root of n.
        
        # Importing the math module to use the sqrt function
        import math
        
        # Return the integer part of the square root of n
        return int(math.sqrt(n))

class Solution {
public:
    int bulbSwitch(int n) {
        // Explanation:
        // Each bulb is toggled in each round where the round number is a divisor of the bulb's position.
        // For example:
        // - Bulb 1 is toggled in every round (1st, 2nd, 3rd, ... nth) because 1 divides every integer.
        // - Bulb 2 is toggled in rounds 1 and 2 (since 2 is divisible by both 1 and 2).
        // - Bulb 3 is toggled in rounds 1 and 3 (since 3 is divisible by both 1 and 3).
        //
        // A bulb ends up ON if and only if it's toggled an odd number of times.
        // Only bulbs that are at perfect square positions are toggled an odd number of times.
        // This is because perfect squares have an odd number of divisors.
        // Example: The divisors of 16 are 1, 2, 4, 8, and 16. 
        // Every other number has divisors in pairs, resulting in an even number of toggles.
        //
        // Therefore, the number of bulbs that remain ON is equal to the number of perfect squares ≤ n.
        // The number of perfect squares less than or equal to n is simply the integer part of the square root of n.

        return (int)sqrt(n);  // Returns the number of perfect squares <= n
    }
};

var bulbSwitch = function(n) {
    // The key observation here is that a bulb will end up ON only if it is toggled an odd number of times.
    // A bulb is toggled in every round that is a divisor of its position number.
    // For example, bulb 6 is toggled in rounds 1, 2, 3, and 6 (since these are its divisors).
    // A bulb ends up being ON only if it has an odd number of divisors, which happens when the position number is a perfect square.
    // This is because divisors generally come in pairs (e.g., for 6, divisors are 1 and 6, 2 and 3),
    // but a perfect square (e.g., 9) has one unpaired divisor (e.g., 3 * 3).
    
    // Therefore, the number of bulbs that remain ON corresponds to the number of perfect squares <= n.

    // The number of perfect squares less than or equal to n is simply the largest integer k such that k^2 <= n.
    // This is equivalent to taking the square root of n and rounding it down.

    return Math.floor(Math.sqrt(n));
};

class Solution {
    public int bulbSwitch(int n) {
        // The key observation is that a bulb will be ON after all the rounds 
        // if and only if it is toggled an odd number of times.
        // A bulb is toggled in every round that is a divisor of its position.
        // For example, bulb 12 is toggled in rounds 1, 2, 3, 4, 6, and 12 (its divisors).
        // Normally, divisors come in pairs (e.g., 1 and 12, 2 and 6, 3 and 4),
        // but when the number is a perfect square (e.g., 9 has divisors 1, 3, and 9),
        // one divisor is repeated (3 * 3 = 9), making the total number of divisors odd.
        
        // Thus, bulbs that are perfect squares will remain ON because they are toggled an odd number of times.
        // To count how many bulbs remain ON, we need to find out how many perfect squares are <= n.
        // The number of perfect squares <= n is simply the largest integer k such that k^2 <= n.
        // This is equivalent to taking the square root of n and rounding it down.

        // Math.sqrt(n) gives the square root of n.
        // We cast it to int because we only care about the integer part (floor of the square root).
        return (int) Math.sqrt(n);
    }
}