Folioevanzhou.org
← 返回 Kata
MediumLeetCode2026-06-22原题 ↗

042Bulb Switcher

math

Problem

有 n 个灯泡,编号从 1 到 n。

一开始,所有灯泡都是关闭的。

接下来会进行 n 轮操作:

  • 第 1 轮:切换所有灯泡的状态
  • 第 2 轮:切换编号是 2 的倍数的灯泡
  • 第 3 轮:切换编号是 3 的倍数的灯泡
  • ...
  • 第 i 轮:切换编号是 i 的倍数的灯泡
  • ...
  • 第 n 轮:只切换编号是 n 的倍数的灯泡

“切换”表示:

  • 如果灯泡原来是关闭的,就变成打开
  • 如果灯泡原来是打开的,就变成关闭

请返回:经过 n 轮操作以后,还有多少个灯泡是打开的。

例如:

n = 3

一开始:

[off, off, off]

第 1 轮,切换所有灯泡:

[on, on, on]

第 2 轮,切换编号是 2 的倍数的灯泡,也就是第 2 个灯泡:

[on, off, on]

第 3 轮,切换编号是 3 的倍数的灯泡,也就是第 3 个灯泡:

[on, off, off]

最后只有第 1 个灯泡是打开的,所以答案是:

1

Examples

示例 1

Input:  n = 3
Output: 1

解释:经过三轮切换后,只有第 1 个灯泡保持打开。

示例 2

Input:  n = 0
Output: 0

解释:没有灯泡,也没有需要操作的轮次,所以打开的灯泡数量是 0。

示例 3

Input:  n = 1
Output: 1

解释:第 1 轮会切换唯一的灯泡,所以最后它是打开的。

Constraints

  • 0≤0 \leq n ≤109\leq 10^9

最初怎么想、怎样补完整、最后如何落成。