Python程序：计算n个人翻动开关后，最终亮着的开关数量

假设我们有一个数字n，房间里有n个开关，所有开关都处于关闭状态。现在有n个人依次翻动开关，如下所示：

  • 第1个人翻动所有是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]

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

  • l := 0, r := n
  • 当 l <= r 时，执行以下操作：
    • mid := l +(r - l) / 2
    • 如果 mid^2 <= n < (mid + 1)^2，则
      • 返回 mid
    • 否则，如果 n < mid^2，则
      • r := mid
    • 否则，
      • l := mid + 1

让我们看看下面的实现以更好地理解：

示例

在线演示

class Solution:
   def solve(self, 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

ob = Solution()
n = 5
print(ob.solve(n))

输入

5

输出

2

更新于：2020年12月2日

343 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告