Leetcode 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 nth 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.

如果直接按照题目给出的思路来解答，会导致超时。

观察后可以看出一下的过程，假设我们观察第9个灯泡，这个灯泡会在第1, 3, 9轮中分别被toggle一次，所以最后会保持点亮。第10个灯泡，会在1,2,5,10轮被toggle四次，最后保持熄灭。

所以如果一个数的因子个数是奇数个，那么这个灯泡最后就是点亮的。反之，这个灯泡最后就是熄灭的。显然之后完全平方数才有奇数个因子，因为因子都是成对儿出现的。

所以这个问题其实就是问，<=n的正整数中有多少个完全平方数。也就是<= sqrt(n) 的最大正整数是哪个？

return int(math.sqrt(n))

巴特西

Leetcode Bulb Switcher

最新文章

热门文章