英文原文
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.
Return the number of bulbs that are on after n rounds.
Example 1:
Input: n = 3 Output: 1 Explanation: At first, the three bulbs are [off, off, off]. After the first round, the three bulbs are [on, on, on]. After the second round, the three bulbs are [on, off, on]. After the third round, the three bulbs are [on, off, off]. So you should return 1 because there is only one bulb is on.
Example 2:
Input: n = 0 Output: 0
Example 3:
Input: n = 1 Output: 1
Constraints:
0 <= n <= 109
中文题目
初始时有 n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭一个。
第三轮，你每三个灯泡就切换一个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换一个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。
找出并返回 n 轮后有多少个亮着的灯泡。
示例 1：
输入：n = 3 输出：1 解释： 初始时, 灯泡状态 [关闭, 关闭, 关闭]. 第一轮后, 灯泡状态 [开启, 开启, 开启]. 第二轮后, 灯泡状态 [开启, 关闭, 开启]. 第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 你应该返回 1，因为只有一个灯泡还亮着。
示例 2：
输入：n = 0 输出：0
示例 3：
输入：n = 1 输出：1
提示：
0 <= n <= 109
通过代码
高赞题解
数学
这是一道经典的数论题。
整理一下题意：第 $i$ 轮改变所有编号为 $i$ 的倍数的灯泡的状态（其中灯泡编号从 $1$ 开始）。
一个编号为 $x$ 的灯泡经过 $n$ 轮后处于打开状态的充要条件为「该灯泡被切换状态次数为奇数次」。
同时，一个灯泡切换状态的次数为其约数的个数（去重）。
于是问题转换为：在 $[1,n]$ 内有多少个数，其约数的个数为奇数。这些约数个数为奇数的灯泡就是最后亮着的灯泡。
又根据「约数」的定义，我们知道如果某个数 $k$ 为 $x$ 的约数，那么 $\frac{x}{k}$ 亦为 $x$ 的约数，即「约数」总是成对出现，那么某个数的约数个数为奇数，意味着某个约数在分解过程中出现了 $2$ 次，且必然重复出现在同一次拆解中，即 $k = \frac{x}{k}$，即有 $x$ 为完全平方数（反之亦然）。
问题最终转换为：在 $[1,n]$ 中完全平方数的个数为多少。
根据数论推论，$[1,n]$ 中完全平方数的个数为 $\left \lfloor \sqrt{n} \right \rfloor$，即最后亮着的灯泡数量为 $\left \lfloor \sqrt{n} \right \rfloor$。
代码：
[]class Solution { public int bulbSwitch(int n) { return (int)Math.sqrt(n); } }
- 时间复杂度：$O(1)$
- 空间复杂度：$O(1)$
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/
也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 48310 | 84670 | 57.1% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
相似题目
| 题目 | 难度 |
|---|---|
| 灯泡开关 Ⅱ | 中等 |
| K 连续位的最小翻转次数 | 困难 |
