Chương trình đếm số công tắc sẽ bật sau khi lật bởi n người trong python

Giả sử chúng ta có một số n, và có n công tắc trong phòng và tất cả các công tắc đều tắt. Bây giờ có n người lật công tắc như sau -

• Người 1 lật tất cả các công tắc là bội số của 1 (vì vậy tất cả các công tắc).
• Người 2 lật các công tắc là bội số của 2 (2, 4, 6, ...)
• Người tôi bật các công tắc là bội số của tôi.

Chúng tôi phải tìm số công tắc sẽ bật ở cuối.

Vì vậy, nếu đầu vào là n =5, thì đầu ra sẽ là 2, vì ban đầu tất cả đều tắt [0, 0, 0, 0, 0], Người 1 đã lật tất cả [1, 1, 1, 1, 1] , Người 2 đã lật như [1, 0, 1, 0, 1], sau đó Người 3 thực hiện [1, 0, 0, 0, 0], người 4 thực hiện [1, 0, 0, 1, 0]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• l:=0, r:=n
• trong khi l <=r, thực hiện
  • giữa:=l + (r - l) / 2
  • nếu giữa ^ 2 <=n <(giữa + 1) ^ 2, thì
    • trở lại giữa chừng
  • ngược lại khi n
  • r:=mid
• nếu không,
  • l:=mid + 1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

5

Đầu ra

2