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.

---

Solution:

Couple observations:

For nth bulb, if will be toggled by all his divisors. For example, 8th bulb, it will be initialized as off, it will be toggled to on at the first round, toggled off at the second round, toggled on at the fourth round, toggled off again at the 8th round. So if n has even number of divisor, the status of the bulb will be off eventually. Most numbers have even number of divisors except perfect square number like 1,4, 9... which have odd number of divisors, so the final status will be on for those bulbs.

So 1<=n<4, there will be 1 bulb that is on

for 4<=n<9, where will be 2 bulbs that are on

So the answer to this problem will be just the square root of n.

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