导航
导航
文章目录
  1. 题目
  2. 翻译

LeetCode-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 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个灯泡,初始状态为关闭。首先打开所有的灯泡。然后,每隔一个关闭。在第三轮,每三个灯泡切换其状态(关闭则打开,打开则关闭)。在第n轮,只切换最后一个灯泡的状态。找出在n轮过后有几个灯泡是打开的。
例如:
给出n=3。
一开始,三个灯泡为 [关 关 关]。
第一轮结束,三个灯泡为 [开 开 开]。
第二轮结束,三个灯泡为 [开 关 开]。
第三轮结束,三个灯泡为 [开 关 关]。
所以应当返回1,因为只有一个灯泡是开着的。

可以循环模拟整个开关过程,非常耗时。
其实是数学问题,从1到n共n轮,初始状态为关闭,所以最后只有被切换了奇数次的灯泡是亮着的,即其编号包含奇数个因子(包括1和其本身)的灯泡最后是亮着的。
而对于任意正整数n,当n为平方数时,其因子数(包括1和n本身)为奇数,当n为非平方数时,其因子数(包括1和n本身)为偶数,因此小于等于n的平方数的个数,即为所求:

1
2
3
4
5
public class Solution {
public int bulbSwitch(int n) {
return (int)Math.sqrt(n);
}
}