LeetCode 319. 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.
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-1到n时，新加上去的一次操作是判断从[1,n]里面n的因子个数，这里记作f(n)好了，即a[n] = a[n-1] + f(n)
因子个数的求法可以精简一下时间，排除0,1,2这三个特殊值后，计算[2, sqrt(n)]里头能整除的数的个数就行了，如果碰到个平方数那个数+1，不然个数就是+2的（i能被n整除，那么它的补数n/i也行）。
这个方法的复杂度嘛，O(n^1.5)吧

class Solution {
public:
    int factors(int n){
        if(n == 0){
            return 0;
        } else if(n == 1){
            return 1;
        } else if(n == 2){
            return 2;
        }
        int count = 2;  //1和自己
        int sqr = (int)(sqrt(n));
        for(int i=2; i <= sqr; i++){
            if(n % i == 0){
                if(i *i == n)
                    count += 1; //平方数
                else
                    count += 2; //一个数和它的补数
            }
        }
        return count;
    }
    int bulbSwitch(int n) {
        if(n < 1){
            return 0;
        }
        int bCount = 0;
        for(int i=1; i<=n; i++){
            if((factors(i)&1) == 1){
                bCount ++;
            }
        }
        return bCount;
    }
};

智商碾压，O(1)解

真正的奥义用一行代码就能解释

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

呵呵哒！这个规律如果多试几次说不定能发现，0,1,1,1,2,2,2,2,2,3这种数列嘛
https://leetcode.com/discuss/91371/share-my-o-1-solution-with-explanation
大概意思是，要在[1,n]里头找哪些灯泡被执行了奇数次操作

•  对于一个非平方数来说（比如12），因为有成对的补数（1vs12; 2vs6），所以总是会按下2的倍数次
• 但是对于一个平方数来说（比如36），因为其中有个数(6)它的补数是自己，所以会按被下奇数次

然后这道题就变成了找[1,n]中间有几个平方数了
OMG…