经典面试题“100盏灯”的数学本质与最优解：从因数奇偶性到完全平方数

1. 问题引入：从一盏灯到一百盏灯的逻辑迷宫

“100盏灯问题”是技术面试中一个非常经典的逻辑与编程结合题。我第一次遇到它是在多年前的一次后端开发岗面试中，面试官没有问任何框架细节，而是抛出了这个问题。当时心里咯噔一下，觉得这像是脑筋急转弯，但静下心来分析后，才发现它完美地考察了候选人的问题拆解能力、逻辑思维，以及将数学洞察转化为代码实现的基本功。这道题之所以经久不衰，是因为它用了一个极其简单的场景，包装了关于因数、奇偶性和完全平方数等多个核心概念，无论你是用Java、Python还是前端JavaScript，都能用它来检验思维清晰度。

简单描述一下场景：一个房间里有编号为1到100的100盏灯，初始状态全部是关闭的。门外有编号为1到100的100个人。第一个人（1号）进入房间，把所有编号是1的倍数的灯的开关按一次（即按遍所有100盏灯）。接着，第二个人（2号）进入房间，把所有编号是2的倍数的灯的开关按一次。以此类推，直到第100个人（100号）进入房间，把所有编号是100的倍数的灯（实际上只有第100盏灯本身）的开关按一次。

问题来了：当这100个人都按完开关离开房间后，请问最终有哪些灯是亮着的？

别急着写循环。我们得先抛开代码，用逻辑和数学的眼光把这个问题看透。这道题表面上考的是模拟，实际上考的是你能否发现规律，避免写出时间复杂度为O(N²)的暴力解法。理解其本质，无论是应对面试，还是锻炼自己的算法思维，都大有裨益。

2. 核心思路拆解：拨开迷雾，寻找开关的数学本质

要解决这个问题，最笨的办法就是模拟：用一个长度为100的布尔数组表示灯的状态，然后写两层循环，外层遍历1到100的人，内层遍历当前人需要操作的灯，进行状态取反。这个方法直观，但效率不是最优，而且没有体现出你对问题的深度理解。

我们需要深入一步：一盏灯的最终状态（亮或灭）由什么决定？答案是它被按动开关的次数。如果被按了奇数次，则状态与初始相反（亮）；如果被按了偶数次，则状态与初始相同（灭）。初始全部是灭的，所以，最终亮着的灯，就是那些被按了奇数次的灯。

那么，关键问题转化为：对于编号为n的灯，它会被哪些人按到？根据规则，第k个人会按所有编号是k的倍数的灯。因此，灯n会被按到，当且仅当k是n的因数（即k能整除n）。所以，灯n被按的次数，就等于它的正因数的个数。

于是，问题的终极形态出现了：在1到100中，找出所有正因数个数为奇数的整数。因为只有这些灯被按了奇数次，最终才会亮着。

那么，什么样的数，其正因数个数是奇数呢？这就是整个问题的画龙点睛之笔。我们可以列举一下：

• 数字1：因数为{1}，个数为1（奇数）。
• 数字2：因数为{1, 2}，个数为2（偶数）。
• 数字3：因数为{1, 3}，个数为2（偶数）。
• 数字4：因数为{1, 2, 4}，个数为3（奇数）。
• 数字5：因数为{1, 5}，个数为2（偶数）。
• 数字6：因数为{1, 2, 3, 6}，个数为4（偶数）。
• 数字9：因数为{1, 3, 9}，个数为3（奇数）。

观察一下亮的灯号：1, 4, 9... 这看起来像是平方数序列。没错，完全平方数的正因数个数是奇数，而非完全平方数的正因数个数是偶数。

2.1 为什么完全平方数的因数个数是奇数？

这是数论中的一个基本性质。对于任意一个正整数n，其因数总是成对出现的（比如d和n/d）。只有当d等于n/d时，这一对因数才会“坍缩”成一个。而d = n/d意味着d² = n，即n是一个完全平方数。此时，这个因数d（即sqrt(n)）被单独计算了一次，导致总因数个数由偶数变成了奇数。

举个例子：

• 数字12（非平方数）：因数对为 (1,12), (2,6), (3,4)。共3对，6个因数（偶数）。
• 数字16（平方数）：因数对为 (1,16), (2,8), (4,4)。这里(4,4)是同一个数，所以因数为1,2,4,8,16。共5个因数（奇数）。

因此，我们得到了最优雅的结论：最终亮着的灯，其编号是完全平方数。

注意：这个结论是解决问题的核心钥匙。在面试中，如果你能直接推导出这一点，并清晰地解释出来，无疑会大大加分。它展示了你的逻辑推理能力和数学直觉。

3. 从数学结论到代码实现

有了“完全平方数”这个结论，代码就变得异常简单。我们不需要模拟100个人的操作过程，只需要找出1到100之间的所有完全平方数即可。

3.1 多种语言实现方案

这里给出几种常见面试语言的实现，并分析其优劣。

Python实现（最简洁）:

def find_lights_math(n=100): """基于数学规律的解法""" lights_on = [] i = 1 while i * i <= n: lights_on.append(i * i) i += 1 return lights_on print(find_lights_math()) # 输出: [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

这种解法的时间复杂度是O(sqrt(N))，空间复杂度是O(k)（k为完全平方数的个数）。这是最优解。

Java实现:

import java.util.ArrayList; import java.util.List; public class HundredLights { public static List<Integer> findLightsMath(int n) { List<Integer> result = new ArrayList<>(); for (int i = 1; i * i <= n; i++) { result.add(i * i); } return result; } public static void main(String[] args) { System.out.println(findLightsMath(100)); // 输出: [1, 4, 9, 16, 25, 36, 49, 64, 81, 100] } }

JavaScript/TypeScript实现 (前端视角):

function findLightsMath(n: number = 100): number[] { const lightsOn: number[] = []; for (let i = 1; i * i <= n; i++) { lightsOn.push(i * i); } return lightsOn; } console.log(findLightsMath()); // [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

3.2 作为对比的模拟解法

虽然数学解法最优，但面试官有时会要求你写出模拟过程，以考察你的基本编码能力。这里也给出模拟解法，并分析其陷阱。

Python模拟解法:

def find_lights_simulate(n=100): """模拟开关过程的解法""" # 初始化灯的状态，False表示灭，True表示亮 lights = [False] * (n + 1) # 索引从0开始，我们使用1-100，所以长度设为n+1 for person in range(1, n + 1): for light in range(person, n + 1, person): # 从person开始，步长为person lights[light] = not lights[light] # 取反操作 # 收集亮着的灯 lights_on = [i for i in range(1, n + 1) if lights[i]] return lights_on print(find_lights_simulate())

模拟解法的时间复杂度是O(N * (N/1 + N/2 + ... + N/N))，这近似于O(N log N)（调和级数），比O(N²)稍好，但远不如O(sqrt(N))的数学解法。空间复杂度为O(N)。

实操心得：在面试中，即使你一眼看出了数学规律，也最好先和面试官沟通你的思路。你可以说：“我观察到这个问题可以转化为求因数的奇偶性问题，进而发现只有完全平方数满足条件。如果需要，我也可以先写出模拟过程的代码。” 这样既展示了你的洞察力，也体现了你扎实的编码基本功。

4. 问题变形与深度考察点

一个优秀的面试官不会只满足于标准答案。围绕“100盏灯”，可以衍生出许多考察点，这些才是区分普通候选人和优秀候选人的关键。

4.1 变形一：初始状态为全亮

如果初始状态100盏灯全是亮的，经过同样的100个人按开关后，哪些灯是灭的？解析：逻辑完全不变。被按奇数次数的灯，状态会改变（从亮变灭）。被按偶数次的灯，状态不变（保持亮）。所以，灭的灯仍然是编号为完全平方数的灯。结论不变，但理解要透彻：奇数次操作改变状态，偶数次操作抵消。

4.2 变形二：第i个人按所有编号为i的倍数的灯，但只按一次（无论之前状态）

这个描述其实和原题一样。但有些候选人会纠结“只按一次”的表述，其实它强调的是每个人的操作是独立的、一次的，不是来回拨动。核心规则没变。

4.3 变形三：如果灯的数量是N，人的数量是M (N != M)

这是更一般的推广。例如，有150盏灯（1-150），但只有100个人（1-100）。问最后哪些灯亮？解析：此时，对于编号大于100的灯，它不会被编号大于它自身的人操作。但规律依然存在：灯n亮，当且仅当它在1到min(n, M)这个范围内，拥有奇数个因数。更准确地说，是拥有奇数个不超过M的因数。如果M >= n，则退化为原问题（看n是否为完全平方数）。如果M < n，则需要找出n在1到M范围内的因数个数是否为奇数。这稍微复杂一些，可能需要遍历判断，或者寻找新的数学规律。

4.4 变形四：求第k盏灯被按了多少次？

这直接回到了我们的核心分析：求数k的正因数个数。你可以写一个函数来计算。

def count_factors(k): count = 0 i = 1 while i * i <= k: # 只需遍历到平方根 if k % i == 0: count += 1 # i是一个因数 if i != k // i: # 避免重复计算平方根 count += 1 # k//i是另一个因数 i += 1 return count print(count_factors(12)) # 输出 6 print(count_factors(16)) # 输出 5

这个函数的时间复杂度是O(sqrt(k))。

4.5 考察点：如何测试你的代码？

面试官可能会问：“你会如何测试这个函数？” 这是一个考察工程思维的好问题。

1. 边界测试：N=0, N=1, N=2。特别是N=1时，应该输出[1]。
2. 小规模验证：手动模拟N=10的情况，与程序输出对比。比如N=10，完全平方数有1,4,9。可以手动推导验证。
3. 大规模验证：用模拟法（虽然慢但正确性容易理解）的结果，去验证数学解法（快）的结果，确保两者在N较大时（如N=10000）仍然一致。
4. 性能测试：对数学解法，输入一个很大的N（如10^12），看其速度。对模拟解法，输入稍大的N（如10^5），感受其性能差异。

5. 在面试中如何展现思考过程

遇到这类问题，不要急于编码。优秀的面试表现在于清晰的沟通和循序渐进的思考。

1. 澄清问题：首先，复述问题以确保理解正确。“您说的是100盏灯初始关闭，100个人按倍数开关，最后问亮灯的对吗？有没有其他边界条件？”
2. 提出暴力解法：先给出最直观的想法。“最直接的方法是模拟，用一个数组记录状态，两层循环进行状态翻转。”
3. 分析复杂度：指出暴力解法的问题。“模拟解法的时间复杂度大概是O(N log N)或O(N²)，空间复杂度O(N)。对于N=100没问题，但如果N很大，效率不高。”
4. 寻找规律：这是关键一步。“我们深入一步，一盏灯的状态取决于它被操作的次数。操作次数等于它的编号的因数个数。所以问题变成：找因数个数是奇数的数。”
5. 数学洞察：给出核心结论。“我想到因数是成对出现的。只有当这个数是完全平方数时，它的平方根因数会单独出现，导致总因数个数为奇数。所以，亮着的灯就是1到100之间的所有完全平方数。”
6. 给出优化解：基于结论写出高效代码。“所以，我们只需要遍历1到10（因为10²=100），输出每个数的平方即可。时间复杂度是O(sqrt(N))。”
7. 代码实现：写出简洁、健壮的代码。注意处理输入参数、边界和返回值。
8. 讨论变形与测试：主动提出可能的变种问题和测试方法，展现思维的全面性。

6. 从问题到工程思维的延伸

这道题不仅仅是一道面试题，它蕴含的思维模式在软件开发中随处可见。

1. 优化意识：从模拟到数学解的跨越，体现了对算法进行“降维打击”的优化思想。在工程中，面对一个耗时的批处理任务，我们是否也能找到类似的内在规律，将O(N²)的复杂度优化到O(N)甚至O(log N)？例如，某些统计问题可以通过前缀和、差分数组来优化。
2. 问题转化能力：将“灯亮灭”转化为“操作次数”，再转化为“因数个数”，最后转化为“完全平方数判断”。这种将业务问题抽象为数学模型的能力，是解决复杂系统设计的关键。比如，设计一个缓存淘汰策略（LRU），其本质是维护一个有序结构；设计一个分布式ID生成器，可能利用了类似雪花算法的位运算思想。
3. 测试与验证：我们提到用慢速但正确的模拟法去验证快速但复杂的数学解法。这对应着工程中的“双写验证”或“影子测试”策略。在新旧系统迁移、算法替换时，用旧逻辑的结果来验证新逻辑，是保证稳定性的有效手段。
4. 边界思维：考虑N=0，N=1的情况。这对应着编程中的防御性编程和边界条件检查。一个健壮的函数必须能处理各种边缘输入。

7. 常见“坑点”与面试失误实录

根据我担任面试官和与同行交流的经验，很多候选人在这个问题上会踩一些坑。

1. 数组下标从0开始导致的Off-by-one错误：这是最常见的错误。在模拟法中，灯编号是1到100，但数组索引通常是0到99。如果不做映射，直接操作lights[person]，会漏掉第1盏灯或导致数组越界。正确的做法是分配长度为101的数组，忽略下标0，或者使用下标减1的映射。

   # 错误示范 lights = [False] * 100 for person in range(100): # person从0到99 for light in range(person, 100, person+1): # 逻辑混乱 ... # 正确示范（使用长度N+1，忽略索引0） lights = [False] * (101) # 索引0-100 for person in range(1, 101): for light in range(person, 101, person): lights[light] = not lights[light]

2. 误解题意，认为第i个人只按第i盏灯：这是没有仔细读题。题目明确是“编号为i的倍数的灯”，是倍数，不是等于。一定要和面试官确认清楚。

3. 只给出答案，没有推导过程：直接回答“1,4,9...100”然后结束。面试官想知道的是你的思维路径，而不是背诵答案。即使你知道结论，也要一步步推导出来。

4. 无法证明“完全平方数因数个数为奇数”：这是核心难点。如果被问到“为什么”，支支吾吾说不出来会很扣分。务必理解并能够清晰阐述“因数成对出现，平方数因数对重合”这个逻辑。

5. 代码冗长，缺乏封装：把所有的逻辑都写在main函数里。更好的做法是写一个接收参数N的函数，提高代码的可读性和可测试性。

6. 忽视扩展性讨论：当面试官问“如果N很大怎么办？”时，只回答“数学解法很快”。可以进一步讨论：如果N大到10^15，你的解法是否依然有效？（数学解法依然有效，因为只需要循环到sqrt(N)，大约10^7.5次迭代，在现代计算机上可行）。这展示了你的 scalability 思考。

8. 不同技术岗位的侧重点

这道题虽然通用，但不同岗位的面试官关注点可能不同。

• 后端/算法岗：最关注数学规律的推导、时间/空间复杂度分析、变种问题的解决思路。可能会深入问及因数个数计算的更优算法（如利用质因数分解公式）。
• 前端岗：除了逻辑，可能关注代码的清晰度、函数封装，以及能否用前端方式演示这个过程（例如用HTML/CSS/JS动态展示100个灯泡的开关过程）。这考察将逻辑转化为可视化交互的能力。
• 测试岗：可能会非常关注测试用例的设计。如何设计测试用例来覆盖边界情况、错误情况？如何验证结果的正确性？这正好对应了我们前面讲的测试策略。
• 嵌入式/硬件相关岗：可能会引申到位操作。灯的开关状态可以用一个二进制位来表示，100盏灯可以用100个bit（如两个64位整数）来存储。按开关操作可以用**异或(XOR)**运算来高效模拟。这考察了位运算和空间优化能力。

  // 简化的C语言思路，用位域或整数数组 unsigned long long lights_low = 0; // 表示1-64号灯 unsigned long long lights_high = 0; // 表示65-100号灯，实际用不到所有位 // 第k个人操作：将所有k的倍数的bit取反。这需要一些位运算技巧。

无论面对哪个岗位，理解问题本质、清晰沟通、写出健壮代码，这些都是共通的加分项。这道“100盏灯”就像一块试金石，能照出一个程序员的基础思维是扎实还是浮夸。下次面试再遇到它，希望你能从容地拨动逻辑的开关，让思路清晰亮起。