程序计算python中n个人翻转后将打开的开关数量
假设我们有一个数字n,并且一个房间中有n个开关,并且所有开关都处于关闭状态。现在n个按如下所示翻转开关的人-
人员1翻转所有为1的倍数的开关(因此所有开关)。
Person2拨动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、0],人员4进行了[1、0、0、1、0]
为了解决这个问题,我们将遵循以下步骤-
l:=0,r:=n
当l<=r时
l:=中+1
r:=中
返回中
中:=l+(r-l)/2
如果mid^2<=n<(mid+1)^2,则
否则当n<mid^2时
除此以外,
让我们看下面的实现以更好地理解-
例
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