Bulb Switcher - Leetcode Solution

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.

1