---

0319. 灯泡开关

• 标签：脑筋急转弯、数学
• 难度：中等

题目链接

• 0319. 灯泡开关 - 力扣

题目大意

描述：

初始时有 $n$ 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭第二个。

第三轮，你每三个灯泡就切换第三个灯泡的开关（即，打开变关闭，关闭变打开）。第 $i$ 轮，你每 $i$ 个灯泡就切换第 $i$ 个灯泡的开关。直到第 $n$ 轮，你只需要切换最后一个灯泡的开关。

要求：

找出并返回 $n$ 轮后有多少个亮着的灯泡。

说明：

• $0 \le n \le 10^{9}$。

示例：

• 示例 1：

输入：n = 3
输出：1 
解释：
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 

你应该返回 1，因为只有一个灯泡还亮着。

• 示例 2：

输入：n = 0
输出：0

解题思路

思路 1：数学分析

通过分析灯泡的开关规律，我们可以发现一个重要的数学性质：第 $i$ 个灯泡最终的状态取决于它被切换了多少次。

具体分析：

1. 第 $i$ 个灯泡在第 $j$ 轮会被切换，当且仅当 $j$ 是 $i$ 的因子。
2. 因此，第 $i$ 个灯泡被切换的次数等于 $i$ 的因子个数。
3. 如果一个数有奇数个因子，那么它最终会亮着；如果有偶数个因子，那么它最终会关闭。
4. 只有完全平方数有奇数个因子，因为因子总是成对出现的，除了完全平方数的平方根。

因此，答案就是小于等于 $n$ 的完全平方数的个数，即 $\lfloor \sqrt{n} \rfloor$。

思路 1：代码

class Solution:
    def bulbSwitch(self, n: int) -> int:
        return int(n ** 0.5)

思路 1：复杂度分析

• 时间复杂度：$O(1)$，只需要计算一次平方根。
• 空间复杂度：$O(1)$，只使用了常数额外空间。