319. Bulb Switcher

这道题考分析，题目要求从1到n每次按其倍数改变灯泡状态，对于灯泡i来说，i的约数要不是偶数个要不是奇数个，奇数个约数的数是完全平方数(square number)，所以题目转变成从1到n找完全平方数的个数，即sqrt(n)
O(logn) time O(1) space

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

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

    int mySqrt(int n) {
        int lo = 0, hi = n;
        while (lo < hi) {
            long m = (lo + hi + 1) / 2;
            long p = m * m;
            if (p <= n) {
                lo = m;
            } else {
                hi = m - 1;
            }
        }
        return lo;
    }
};

O(sqrt(n)) time O(1) space

class Solution {
public:
    int bulbSwitch(int n) {
        int res = 0;
        for (int i = 1; i * i <= n; ++i) {
            ++res;
        }
        return res;
    }
};