在Python中编写的翻转n个开关后将打开的开关数进行计数的程序

在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,0,1,0,1],然后第三个人做[1,0,0,0,0],第四个人做[1,0,0,1,0]

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

  • l:=0,r:=n
  • 当l<= r时,执行以下内容
    • mid:= l +(r-l)/ 2
    • 如果mid ^ 2 ≦ n<(mid +1)^ 2,则
      • 返回中间值
    • 否则,当n<mid ^ 2时,那么
      • r:= mid
    • 否则,
      • l:= mid +1

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

更多Python相关文章,请阅读:Python 教程

示例

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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程