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. Find how many bulbs are on after n rounds.
You can find the problem at https://leetcode.com/problems/bulb-switcher/.
I’m not going to talk about how to actually code the problem here, just want to share how I thought and finally got to the best solution.
The very naive way would be, create an array of length n, then loop through the array n times to switch the bulbs. This will work, but obviously comes with a O(n^2) time complexity. For that, Leetcode will not pass your solution, and we don’t like an algorithm at O(n^2). OK, then there must be something nicer and quicker to do the job. Let’s think about it.
Assume n is big enough, at the first round, we switch all bulbs:
[On, On, On, … , On]
At the second round ,we switch every two bulbs:
[On, Off, On, Off, … , On] (if n is an odd number) [On, Off, On, Off, … , Off] (if n is an even number)
At the third round, we switch every three bulbs:
[On, Off, Off, Off, On, On, On, … , Off] (if n is an odd number and it could be divided by 3) [On, Off, Off, Off, On, On, On, … , On] (if n is an odd number and it could not be divided by 3) [On, Off, Off, Off, On, On, On, … , On] (if n is an even number and it could be divided by 3) [On, Off, Off, Off, On, On, On, … , Off] (if n is an even number and it could not be divided by 3)
Hmmm, cannot get any pattern till now. But we can see, as the count of round goes up, the former part of array will not be touched anymore. Let’s give a position number to all the bulbs, starting from 1 to n.
[1, 2, 3, …, n]
And switch the words one, two, three to number 1, 2, 3 … n. OK, so before the round reaches a particular number (bulb), it could be switched one or more times. After that, it will remain the same status. How can we know how many times will a bulb be switched? A straight idea is to find its divisors.
It is easy to understand that, in this situation, a number (bulb) will only be reached when the count of round is a divisor of it. You could also call it prime factors. For example:
- Bulb at position 6 will be switched at 1st, 2nd, 3rd and 6th round.
- Bulb at position 69 will be switched at 1st, 3rd 23th and 69th round.
And so on! Then we know how to calculate the times of a given number is reached. Suppose we have a good algorithm to get all divisors of a number, we can get the solution to the number much more quicker. From this chart, it seems like a number k will have much less number of divisors: https://www.math.upenn.edu/~deturck/m170/wk2/divisors.html. Maybe the average time complexity will decrease to less than O(n/2)? You loop through all numbers and see if the bulb at this position will be on at last. The code looks like:
However, this solution didn’t pass because it is using too much time. So I had to re-think about the algorithm I applied. I thought it about an hour (yes, very long time) and suddenly noticed that the divisors are all in pairs! This is really an a-ha moment for me when solving this problem. Let’s see:
- Position 6: divisors are [1, 6], [2, 3]
- Position 69: divisors are [1, 69], [3, 23]
Did you think of anything? When a bulb is toggled twice, it will be off. So the bulb at #6 and #69 will be off at last. They will not be counted into the number of bulbs are on. But there must be some bulbs remain on when the loop is ended. Which numbers? From the above examples, we can see at least position #1 is on. But why it is one? Because it only have one divisor “1”. Just think a little bit deeper, or you have listed enough examples to observe the divisor pairs, you will find out:
- Position 9: divisors are [1, 9], [3, 3]
- Position 16: divisors are [1, 16], [2, 8], [4, 4]
A-ha! A bulb at position with a number which is perfect square will survive! That’s the critical point. If you still not getting, let me explain it.
We are looping all the bulbs, skipping one more bulb after every round; Consider every position has its number, it will only be reached when the round number is a divisor of its position number; Divisor appears in pairs, unless the divisor is a square root of the position number; A square root will only be reached once, bulb will be toggled only once at [square root]th round. At all the other rounds, the bulb will be toggled on-then-off.
The conclusion is, only the bulbs at a position which order number is a perfect square, will the bulb be on at last. We just need to find out how many perfect squares are there in range [1, n] (inclusive). The code will look like:
def bulbSwitch(self, n): """ :type n: int :rtype: int """ count = 0 i = 1 while i < n + 1: if i ** 2
Why stop when i ** 2 greater than n? Because you have already found the square roots of all the perfect squares within the range, no need to loop further. So someone even gave better solution: just return int(math.sqrt(n)) and this will be the answer.
That’s it. Please leave any comment if you think I’m wrong or you have suggestions for my expressions (as I’m not a native English speaker, just want to make myself more clear on explaining an algorithm problem).