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.

Example:

1
2
3
4
5
6
7
8
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.

思路

首先来看一个很傻的超时方法(用不用哈希表都超时)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def bulbSwitch(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 0:
            return 0
        bulbmap = {}
        length = n
        while(n > 1):
            i = 1
            while(n * i <= length):
                index = n * i
                if (bulbmap.has_key(index)):
                    bulbmap[index] = not bulbmap[index]
                else:
                    bulbmap[index] = False
                i += 1
            n -= 1
        count = 0
        for i in bulbmap.values():
            count += i
        return count + 1

其实，如果一个数是完全平方数，他会被自己本身trigger，还会被自己的完全平方数trigger。所以那个数对应的那盏灯还是会亮；如果一个数不是完全平方数，它会被自己trigger，还会被自己分解出来的乘积trigger，所以对应的灯会灭。

1
2
3
4
5
6
7
class Solution(object):
    def bulbSwitch(self, n):
        """
        :type n: int
        :rtype: int
        """
        return int(math.sqrt(n))