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

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

提示	解題應用
Math	規律觀查

Default:

func bulbSwitch(n int) int {

}

解答思路:

一開始是直接照規則用暴力法的方式一輪一輪修正，最後再統計開關打開的數量，而當然不出所以然超過時間，透過規律觀查我們發現到最後開關打開的情況都剛好是燈泡落在平方數編號的位置，因式分解之後就不難發現原因，如編號36來說:

36 = 1 x 36
     2 x 18
     3 x 12
     4 x  9
     6 x  6

如果燈泡的開關是打開的表示一共使用了奇數次才有可能，而每個因數正好代表每次使用其開關的時機，而唯有平方數才會讓因數個數為奇數個(重覆的數字只算一次)，也就是說1~n個燈泡最終有多少個開關是打開的取決於這個範圍之間有多少個平方數，所以將n做開根號就可以得知有多少個平方數，同時也是我們要找的結果。

程式碼解說:

這邊就只是單純使用內建數學函式庫的開根號函數來將n做開根號

func bulbSwitch(n int) int {
    return int(math.Sqrt(float64(n)))
}

完整程式碼:

func bulbSwitch(n int) int {
    return int(math.Sqrt(float64(n)))
}

總結:

有1~n個燈泡(並且都賦予1~n的編號)，一開始開關皆為關閉的狀態，並遵循下列規則:

共需要做n輪
第1輪:     開起全數燈泡的開關
第2輪:     關閉編號為2k的開關
第3~n-1輪: 切換編號3k~(n-1)k的開關(若原本開關為開便將其關閉，反之開關為關便將其打開)
第n輪:     僅切換最後一個開關

透過規律觀查我們發現到最後開關打開的情況都剛好是燈泡落在平方數編號的位置(因為因數個數為奇數個，等同於使用了開關奇數次)，也就是說1~n個燈泡最終有多少個開關是打開的取決於這個範圍之間有多少個平方數，所以將n做開根號就可以得知有多少個平方數，同時也是我們要找的結果。