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 i-th round, you toggle every i bulb. For the n-th round, you only toggle the last bulb. Find how many bulbs are on after n rounds.
Example
Input: 3
Output: 1
Explanation:
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 个灯泡, 第 i 轮就开关第 i 倍数位的灯,问 n 轮之后,还有几盏灯是亮的状态。 这道题的关键点是第i个灯的状态变化只会被其因子回合改变。 比如 第 8 盏灯,只会被 1,2,4,8 回合改变。 因为他们是相互对称的, 所以第 8 盏灯最后的状态是灭的。什么时候灯会是亮着的呢?只有一个数是完全平方数的时候。 这样完全平方数的因子只会出现一次。 所以直接求 sqrt(n) 即是答案。
代码
class Solution {
public int bulbSwitch(int n) {
return (int)Math.sqrt(n);
}
}