使用Python计算n个人翻转的开关数

假设有一个数字n、一个房间里有n个切换器和n个人，他们按照以下方式翻转开关 −

第一个人来翻转所有的开关。
第二个人来翻转那些是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个灯是处于开启状态的

为了解决这个问题，我们将遵循以下步骤−

l := 0
r := n
while l <= r, do
- mid := l + floor of (r – l)/2
- if mid * mid <= n < (mid + 1)^2, then
  - return mid
- 否则，当n < mid^2时，
  - r := mid
- 否则，
  - l := mid + 1

示例

让我们看一下以下实现以更好地理解−

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))