Bulb Switcher

Solution For Bulb Switcher

The Bulb Switcher problem is a popular problem on LeetCode. You are given a number of bulbs that are initially off. You need to turn these bulbs on by flipping them one by one. The rule for flipping the bulbs is as follows: for the Nth bulb, you need to flip all the bulbs that are multiples of N. For example, if N=3, you need to flip bulbs 3, 6, 9, 12, etc.

The problem statement asks for the minimum number of flips required to turn on all the bulbs. The solution to this problem can be derived from an interesting observation. Consider a bulb at position N. If the number of factors of N is odd, the bulb will be switched on after all the flips. If the number of factors is even, the bulb will remain off. The reason for this observation is that a factor pair (a, b) represents two flips at positions a and b.

Using this observation, we can conclude that only the bulbs with a perfect square position will be on at the end. For example, if we have 10 bulbs, only bulbs 1, 4, 9 will be on. Hence, the answer is the number of perfect squares less than or equal to N.

The code implementation of this solution is very simple. We can write a loop to iterate from 1 to N, and for each iteration, we check if the current number is a perfect square. If it is, we increment our answer count.

Here is the Python code for this solution:

class Solution:
def bulbSwitch(self, n: int) -> int:
return int(math.sqrt(n))

This solution has a time complexity of O(sqrt(N)), which is very efficient and can handle even large values of N.

Step by Step Implementation For Bulb Switcher

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the i-th round, you toggle every i bulb. For the n-th round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:

Input: 3
Output: 1 
Explanation: 
At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off]. 

So you should return 1, because there is only one bulb is on.
There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the i-th round, you toggle every i bulb. For the n-th round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:

Input: 3
Output: 1 
Explanation: 
At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off]. 

So you should return 1, because there is only one bulb is on.
There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the i-th round, you toggle every i bulb. For the n-th round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

//Solution: 

/**
 * @param {number} n
 * @return {number}
 */
var bulbSwitch = function(n) {
    
    //Create a variable to store the number of bulbs that are on
    let bulbsOn = 0;
    
    //Loop through the number of rounds
    for(let i = 1; i <= n; i++){
        
        //If the round number is equal to the square root of the total number of bulbs, toggle the bulb on
        if(i*i <= n){
            bulbsOn++;
        }
    }
    
    //Return the number of bulbs that are on
    return bulbsOn;
};
There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the i-th round, you toggle every i bulb. For the n-th round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:

Given n = 3. 

At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off]. 

So you should return 1, because there is only one bulb is on.
There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the i-th round, you toggle every i bulb. For the n-th round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:

Input: 3
Output: 1 
Explanation: 
At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off]. 

So you should return 1, because there is only one bulb is on.


Scroll to Top

Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]