Bulb Switcher

https://leetcode.com/problems/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.

Thoughts

n个灯泡，初始时全灭，在第i轮, 从第i个开始每i个灯泡做一次开关切换，问n轮后有多少灯泡是亮的。 对于第i栈灯，当i的因子数为奇数时最后是亮的，如9的因子有1，3，9，也就是在且只在第1, 3和9轮会动到第9个灯泡；否则是灭的。而且只有完全平方数才有奇数个因子，分别为1,...,sqrt(i),...i。求N之前有几个数有平方根用sqrt(N)，比如N = 36 = 6 ^ 2, 那么6^2和之前的1^2, 2 ^ 2, 3^2, 4^2, 5^2有平方根。

Code

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

Analysis

求根, O(lgN).