Bulb Switcher

Leetcode 319. Bulb Switcher

Problem

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 ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb.

Return the number of bulbs that are on after n rounds.

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

Constraints:

• 0 <= n <= 109

Source: Leetcode 319. Bulb Switcher

Solution

We can solve this problem by analyzing with some sample test cases.

Let’s say we have 2 bulbs. The scenario for 2 bulbs will be like below where we will have 1 bulb remaining to be on.

From this only, we can derive that, if n = 2, we will have n / 2 remaining bulbs on.

Is this assumption true for all value of n? Let’s say, if we have 5 bulbs, we should have 5 / 2 = 2 bulbs remaining on.

Let’s see if this assumption true or not seeing below image.

Yes, it is true for 5 as well! Still, we need to check more. How about n = 9?

Nope, it’s not true for n = 9 🙁 Because 9 / 2 = 4 and we can see there are 3 bulbs left on from the image. So, what could be a perfect formula for this?

Well, we have to play with more numbers. Let’s grab a pencil and paper and check what happens for n = 10, 11, 12 etc. Do this fun exercise and come back here again 🙂

We did this fun exercise for you and found that, the magic formula is to take square root of n. If we take sqrt(n), we get the finally remaining on bulb numbers. Can this be proved mathematically? Probably yes, but we do not this yet. If you do, please leave your explanation in the comment section!

C++ Code

class Solution {
public:
    int bulbSwitch(int n) {
        return (int) sqrt(n);        
    }
};

Conclusion

Hope you enjoyed this solution analysis and the code. Please write us your comments about how we can improve this blog! Happy Coding 🙂