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

解答：

我們知道，每當燈泡會改變狀態，也就是 toggle 時，是因為它出現在了某個數的整數倍上。

對於第1個燈泡：1*1，會改變1次狀態，即 off -》on

對於第2個燈泡：1*2，2*1，會改變2次狀態，即 off -》on -》off

對於第3個燈泡：1*3，3*1，會改變2次狀態，即 off -》on -》off

對於第4個燈泡：1*4，2*2，4*1，會改變3次狀態，即 off -》on -》off -》on

……

會發現，每當我找到一個數的整數倍，總會找到對稱的一個整數倍，例如 1*2，就肯定會有一個 2*1。唯一的例外出現在平方數上，例如 4 = 2*2，只有一次整數倍。

每次作為偶數次整數倍，最終的燈泡都會還原為 off；只有作為奇數次整數倍，最終的燈泡都會 on。

也就是說，最終亮的燈泡數目由小於其的最大平方數確定。代碼非常簡單：

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