042 · Bulb Switcher

algorithm
Published

June 22, 2026

My First Thoughts

嗯，先从几个小的数找找特征和规律：

n = 0 -> 0
n = 1 -> 1
n = 2 -> 1
n = 3 -> 1
n = 4 -> 2
n = 5 -> 2
n = 6 -> 2

这里应该考察的是因子的问题。

因为第 i 轮会切换编号是 i 的倍数的灯泡。反过来看，一个编号为 x 的灯泡，会在哪些轮次被切换，其实就取决于哪些数字可以整除 x。

也就是说：

一个灯泡最后会被切换多少次，等于它的编号有多少个因子。

比如 2：

2 的因子是 1, 2

所以第 2 个灯泡会被切换两次。它一开始是关，切换偶数次以后还是关。

再看 3：

3 的因子是 1, 3

第 3 个灯泡也是切换两次，所以最后也是关。

再看 4：

4 的因子是 1, 2, 4

第 4 个灯泡会被切换三次。切换奇数次，所以最后是开。

继续看：

5 的因子是 1, 5
6 的因子是 1, 2, 3, 6

5 会切换两次，最后是关。6 会切换四次，最后也是关。

所以这里可以得到一个判断：

因子数量是偶数的，灯泡最后一定是关；因子数量是奇数的，灯泡最后一定是开。

因此 n 的结果，就是 1 到 n 里，所有“因子数量为奇数”的数字的个数。这应该就是核心考点。

接下来就可以先考虑：如何求一个数有多少个因子。

粗略地写，可以先有一个 nfactor：

def nfactor(n):
    total = 0

    for i in range(1, int(n ** 0.5)):
        if n % i == 0:
            total += 1

    return total

然后外层遍历 0..n，看每个数字的因子数是不是奇数：

light = 0

for i in range(0, n + 1):
    if nfactor(i) % 2 != 0:
        light += 1

return light

Why That Is Not Enough

解题思路是没错的。

这道题的核心考点就是：

一个数的因子数量是奇数还是偶数

因为第 x 个灯泡会在所有“能整除 x 的轮次”里被切换，所以第 x 个灯泡被切换的次数，就是 x 的因子数量。

真正有问题的是这里的实现：

def nfactor(n):
    total = 0

    for i in range(1, int(n ** 0.5)):
        if n % i == 0:
            total += 1

    return total

如果是希望计算全部因子，那么循环范围应该是：

range(1, n + 1)

这样才是把 1 到 n 每个可能的因子都检查了一遍：

for i in range(1, n + 1):
    if n % i == 0:
        total += 1

如果希望利用 sqrt(n) 来节省计算，那也可以，但加和方式就不能还是 +1。

因为因子是成对出现的。

比如 6：

1 和 6
2 和 3

检查到 1 时，其实同时找到了 1 和 6。
检查到 2 时，其实同时找到了 2 和 3。

所以如果只遍历到平方根，每次发现一个因子，通常应该：

total += 2

只有平方数是例外。

比如 4：

1 和 4
2 和 2

这里 2 和 2 是同一个因子，不能算两次。所以遇到平方根本身时，只能：

total += 1

所以这里的问题可以总结成两层：

  • 如果完整遍历，就应该遍历到 n + 1
  • 如果只遍历到 sqrt(n)，普通因子要 +2，平方根边界要单独 +1

先把这两种修正都写完整。

第一版是完整计算每个数的因子数量：

def nfactor(n):
    total = 0

    for i in range(1, n + 1):
        if n % i == 0:
            total += 1

    return total


def bulbSwitch(n):
    light = 0

    for x in range(1, n + 1):
        if nfactor(x) % 2 != 0:
            light += 1

    return light

这个版本和最初想法完全一致：要知道每个编号有多少个因子，就从 1 到它自己全部检查一遍。

第二版是利用平方根优化。

如果 i 是 x 的因子，那么 x // i 也是 x 的因子。所以只扫到平方根时，命中一个普通因子，就等于找到了两个因子：

i 和 x // i

代码可以写成：

def nfactor(n):
    total = 0

    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            if i * i == n:
                total += 1
            else:
                total += 2

    return total


def bulbSwitch(n):
    light = 0

    for x in range(1, n + 1):
        if nfactor(x) % 2 != 0:
            light += 1

    return light

到这里为止，仍然是在做同一件事：

统计因子数量，再判断奇偶性

只是第二版把“完整遍历数因子”改成了“平方根范围内按因子对计数”。

然后才能继续观察第二版的计数逻辑。

普通因子每次贡献都是：

+2

+2 一定不会改变奇偶性。也就是说，一对一对出现的因子，只会让因子数量保持偶数。

真正会改变奇偶性的，只有平方根那个特殊边界。

也就是：

i * i == x

如果存在这样的 i，说明 x 是一个平方数。平方根这个因子只出现一次，会让因子数量变成奇数。

如果不存在这样的 i，所有因子都成对出现，因子数量就是偶数。

所以问题可以继续转换：

因子数量是不是奇数
= 这个数是不是平方数

最后，题目要统计 1 到 n 中有多少个灯泡是亮的，也就是统计：

1 到 n 中有多少个平方数

这些平方数是：

1^2, 2^2, 3^2, ...

只要平方不超过 n，就说明对应有一个最后亮着的灯泡。

Final Idea

最终思路就是：不用再真的计算每个数有多少个因子，只需要统计 1 到 n 中有多少个平方数。

因为：

  • 非平方数的因子都成对出现，因子数量是偶数
  • 平方数有一个单独的平方根因子，因子数量是奇数

所以最后亮着的灯泡编号一定是：

1^2, 2^2, 3^2, ...

只要不断枚举 i，统计有多少个：

i * i <= n

就能得到答案。

Why It Works

第 x 个灯泡最终是不是亮着，取决于它被切换了多少次。

灯泡 x 被切换的次数 = x 的因子数量

灯泡一开始是关闭的：

  • 切换偶数次，会回到关闭
  • 切换奇数次，会变成打开

所以只要统计因子数量的奇偶性，就能判断灯泡最后的状态。

接下来观察因子的结构。

一般情况下，因子都是成对出现的：

i 和 x // i

比如 6：

1 和 6
2 和 3

每一对贡献两个因子，所以不会改变奇偶性。

只有平方数会出现一个落单的中间因子。

比如 4：

1 和 4
2 和 2

这里 2 只能算一次，所以 4 的因子数量是奇数。

因此，最后亮着的灯泡，正好对应编号是平方数的灯泡。

Code

def bulbSwitch(n):
    light = 0

    i = 1
    while i * i <= n:
        light += 1
        i += 1

    return light

如果保留“检查每个数是不是平方数”的写法，也可以这样理解：

def is_square(x):
    i = 1

    while i * i <= x:
        if i * i == x:
            return True
        i += 1

    return False


def bulbSwitch(n):
    light = 0

    for x in range(1, n + 1):
        if is_square(x):
            light += 1

    return light

第一段代码只是把这个过程再压缩了一步：既然只需要数平方数，就直接数有多少个 i * i <= n。

Complexity

Time \(O(\sqrt n)\) - 只需要枚举 i，直到 i * i > n
Space \(O(1)\) - 只使用计数变量

Takeaway

这题的递进是：灯泡切换次数等于因子数量；因子通常成对出现，所以普通因子贡献偶数；只有平方数的平方根会单独出现一次。因此最后亮着的灯泡，正好是编号为平方数的灯泡。

← Quiz