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個(gè)燈泡，初始狀態(tài)是關(guān)閉的。第一輪，打開(kāi)所有燈泡，第二輪關(guān)掉所有2的倍數(shù)的燈泡，第三輪轉(zhuǎn)換所有3的倍數(shù)的燈泡開(kāi)關(guān)狀態(tài)，以此類推，知道第n輪，轉(zhuǎn)換所有n的倍數(shù)的燈泡開(kāi)關(guān)，找出有幾盞燈泡是開(kāi)著的
算法分析
燈泡開(kāi)始是關(guān)閉狀態(tài)。奇數(shù)次輪以后，為開(kāi)啟狀態(tài)；偶數(shù)次輪后為關(guān)閉狀態(tài)。因此本題也就是轉(zhuǎn)化為尋找小于等于n的數(shù)的因數(shù)的個(gè)數(shù)為奇數(shù)的情況。只有平方數(shù)的因數(shù)為奇數(shù)個(gè)
例如：6的因數(shù)為1，6，2，3；而9的因數(shù)為1，9，3；
Java代碼
public class Solution {
public int bulbSwitch(int n) {
if(n <= 0) return 0;
return (int)Math.sqrt(n);//本題最后轉(zhuǎn)化為求小于等于n的平方數(shù)的個(gè)數(shù)
}
}
