파이썬에서 n명이 뒤집은 후 켜질 스위치 수를 계산하는 프로그램

<시간/>

숫자 n이 있고 방에 n개의 스위치가 있고 모든 스위치가 꺼져 있다고 가정합니다. 이제 다음과 같이 스위치를 뒤집는 n명의 사람들 -

사람 1은 1의 배수인 모든 스위치를 뒤집습니다(따라서 모든 스위치).
사람 2는 2의 배수(2, 4, 6, ...)인 스위치를 뒤집습니다.
사람 i는 i의 배수인 스위치를 뒤집습니다.

마지막에 켜질 스위치의 수를 찾아야 합니다.

따라서 입력이 n =5와 같으면 출력은 2가 됩니다. 처음에는 모두 꺼져 [0, 0, 0, 0, 0]이고 Person 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인 동안, do
- 중간:=l +(r - l) / 2
- mid^2 <=n <(mid + 1)^2이면
  - 중간 반환
- 그렇지 않으면 n
- r :=중간
그렇지 않으면
- l :=중간 + 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))

반환