問(wèn)題描述

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:
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.

問(wèn)題分析

參考了一篇博文。
剛開(kāi)始我想直接按點(diǎn)燈/關(guān)燈的步驟來(lái)得到最終燈的狀態(tài)，這么做非常耗時(shí)。
而其實(shí)這是一道數(shù)學(xué)題，搞懂?dāng)?shù)學(xué)原理，一個(gè)計(jì)算公式就可以得到結(jié)果。
什么樣的燈最后是亮著的呢？那就是被開(kāi)關(guān)奇數(shù)次的，相反，開(kāi)關(guān)偶數(shù)次的最后燈是滅的。例如8 = 2 x 4，2和4是成對(duì)出現(xiàn)的，即一次分解就會(huì)開(kāi)一次燈且關(guān)一次等，而只有9 = 3 x 3這種情況，才會(huì)出現(xiàn)只開(kāi)燈，不關(guān)燈的情況。因此完全平方數(shù)的燈是亮的，其它都是滅的。
因此亮的燈依次為：1²，2²，...，?sqrt(n)?²。

AC代碼

class Solution(object):
    def bulbSwitch(self, n):
        """
        :type n: int
        :rtype: int
        """
        import math
        return int(math.sqrt(n))