用 Python 计算 n 人翻转的灯的数量的程序

假设我们有一个数字 n，考虑一个房间里有 n 个拨动开关，并且那个房间里有 n 个人，他们按如下方式翻转开关 -

• 人 1 来了并翻转了所有开关。

• 人 2 来了，拨动了 2 的倍数的开关：2, 4, 6, ...

• 人 i 来并翻转 i 倍数的开关。等等。

我们必须找到最终将在位置上的开关数量。

因此，如果输入类似于 n = 5，那么输出将为 2，因为最初灯泡是 [0, 0, 0, 0, 0]。

• 在玩家 1 之后：[1, 1, 1, 1, 1]

• 在玩家 2 之后：[1, 0, 1, 0, 1]

• 在玩家 3 之后：[1, 0, 0, 0, 1]

• 在玩家 4 之后：[1, 0, 0, 1, 1]

• 玩家 5 之后：[1, 0, 0, 1, 0]

最后有2个灯处于ON状态

示例

让我们看看以下实现以获得更好的理解 -

def solve(n):
   l, r = 0, n
   while l <= r:
      mid = l + (r - l) // 2
      if mid * mid <= n < (mid + 1) * (mid + 1):
         return mid
      elif n < mid * mid:
         r = mid
      else:
         l = mid + 1

n = 5
print(solve(n))

输入

5

2