Bulb Switcher解题报告

Description:

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.

Link:

https://leetcode.com/problems/bulb-switcher/description/

解题方法：

一开始用brute force，妥妥的超时，看过discuss以后才知道以下解法：

比如从上面例子当n = 3时，有[on, off, off]
当n = 4时，前面三个灯泡与n = 3时相同，所以取决于第四个💡是不是亮。
所以，
第几个💡是亮还是灭，取决于它被toggle几次，也就是取决于它有几个系数，比如第四个灯泡的系数为：1，2，4。这个灯泡就是亮的。
由此上信息可以知道，想知道第几个灯泡是亮还是灭，只要知道它系数的个数是奇数（亮）还是偶数（灭）。
而当一个数是平方数的时候，它的系数个数是奇数个。
所以，本题的解答变成统计从1~n有多少个平方数，即为从1~n有多少个亮的💡。

Time Complexity：

O[N^(1/2)]

完整代码：

int bulbSwitch(int n) 
    {
        if(n == 0)
            return 0;
        int count = 0;
        for(int i = 1; i*i <= n; i++ )
            count++;
        return count;
    }