leetcode筆記：Bulb Switcher

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.

二. 題目分析

題目大意是，有n只初始處於關閉狀態的燈泡。你首先打開所有的燈泡（第一輪）。然後，熄滅所有序號為2的倍數的燈泡。第三輪，切換所有序號為3的倍數的燈泡（開著的就關掉，關著的就打開）。第n輪，你只切換最後一只燈泡。計算n輪之後還有幾盞燈泡亮著。

先看看以下規律：

第1個燈泡：1的倍數，會改變1次狀態： off -> on

第2個燈泡：1的倍數，2的倍數，會改變2次狀態： off -> on -> off

第3個燈泡：1的倍數，3的倍數，會改變2次狀態： off -> on -> off

第4個燈泡：1的倍數，2的倍數，4的倍數，會改變3次狀態： off -> on -> off -> on

第5個燈泡：1的倍數、5的倍數，會改變2次狀態： off -> on -> off

第6個燈泡：1的倍數，2的倍數，3的倍數，6的倍數，會改變4次狀態： off -> on -> off -> on -> off

第7個燈泡：1的倍數、7的倍數，會改變2次狀態： off -> on -> off

第8個燈泡：1的倍數，2的倍數，4的倍數，8的倍數，會改變4次狀態： off -> on -> off -> on -> off

第9個燈泡：1的倍數，2的倍數，4的倍數，會改變3次狀態： off -> on -> off -> on

……

通過上面的描述可以發現，對於n = 2,3,5,6,7,8，找到一個數的整數倍，總會找到對稱的一個整數倍，例如 1 * 2，就肯定會有一個 2 * 1。因此這些編號的燈泡會改變偶數次，最終結果肯定為off。

只有當n = 1,4,9這類完全平方數，有奇數次變化，最終的燈泡都會 on。

只要能得出以上結論，用一句代碼就可以解決問題。

三. 示例代碼

class Solution {
public:
    int bulbSwitch(int n) {
        return sqrt(n);
    }
};

四. 小結

對於一些組合類的算法題，找規律比直接動手實現更為重要。