What is the fastest way to solve Bulb Switcher without simulating rounds?

Compute the integer square root of n. Each perfect square bulb remains on, so this count gives the correct answer instantly.

Why do only perfect square bulbs stay on in Bulb Switcher?

Bulbs toggle once for each factor. Non-square numbers have factors in pairs, resulting in an even toggle count (off), while perfect squares have an odd count (on).

Can I simulate each toggle round for Bulb Switcher?

Simulation works for small n, but it is inefficient and will fail for large n due to time complexity. Using the perfect square method is recommended.

Does the solution change for very large n?

No. The solution remains O(1) and uses integer square root calculation, handling n up to 10^9 efficiently.

Is this problem primarily math or algorithm focused?

Bulb Switcher combines Math and Brainteaser patterns, requiring insight into divisors and toggle behavior rather than traditional algorithmic loops.

#319

Medium

auto_awesome数学·结合·brainteaser

LeetCode 题解工作台

灯泡开关

初始时有 n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭第二个。第三轮，你每三个灯泡就切换第三个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换第 i 个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。找出并返回 …

数学脑筋急转弯

题目描述

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

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

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

示例 1：

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

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

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：1

提示：

0 <= n <= 10⁹

lightbulb

解题思路

方法一：数学

我们不妨将 $n$ 个灯泡编号为 $1, 2, 3, \cdots, n$ ，那么对于第 $i$ 个灯泡，它会在第 $d$ 轮被操作，当且仅当 $d$ 是 $i$ 的因子。

对于一个数 $i$ ，它的因子个数是有限的，且因子个数为奇数时，最后的状态是开启的，否则是关闭的。

因此，我们只需要找到 $1$ 到 $n$ 中因子个数为奇数的数的个数即可。

对于一个数 $i$ ，如果它有因子 $d$ ，那么它一定有因子 $i/d$ ，因此因子个数为奇数的数一定是平方数。

举个例子，数字 $12$ 的因子有 $1, 2, 3, 4, 6, 12$ ，因子个数为 $6$ ，是偶数；而对于数字 $16$ 这个平方数，因子有 $1, 2, 4, 8, 16$ ，因子个数为 $5$ ，是奇数。

因此，我们只需要找到 $1$ 到 $n$ 中有多少个平方数即可，即 $\lfloor \sqrt{n} \rfloor$ 。

时间复杂度 $O(1)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

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

speed

复杂度分析

指标	值
时间	complexity is O(1) because only the integer square root calculation is needed. Space complexity is O(1) as no additional storage is required for tracking bulb states.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Expect candidates to identify the divisor pattern instead of iterating through rounds.
question_mark
Look for recognition that only perfect squares have an odd number of factors.
question_mark
Candidates may attempt simulation first, signaling partial understanding of the toggle logic.

warning

常见陷阱

外企场景

error
Simulating each round leads to timeouts for large n values.
error
Failing to connect bulb toggles with number of divisors results in incorrect counting.
error
Misinterpreting the pattern and counting all bulbs rather than just perfect squares.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to count bulbs off after n rounds instead of on, still relying on perfect square logic.
arrow_right_alt
Introduce multiple toggle sequences with different step sizes to test mathematical generalization.
arrow_right_alt
Consider circular bulb arrangements where toggles wrap around, requiring adjusted divisor logic.

help

常见问题

外企场景

继续练习

#292 Nim 游戏 #810 黑板异或游戏 #1025 除数博弈