파이썬에서 n명이 뒤집은 조명의 수를 세는 프로그램

<시간/>

숫자 n이 있다고 가정하고 방에 n개의 토글 스위치가 있고 그 방에 n명의 사람이 있다고 가정하면 다음과 같이 스위치를 켭니다. -

사람 1이 와서 모든 스위치를 켭니다.
사람 2가 와서 2:2, 4, 6, ...의 배수인 스위치를 켭니다.
사람 i가 와서 i의 배수인 스위치를 켭니다. 등등.

마지막으로 온 위치에 있을 스위치의 수를 찾아야 합니다.

따라서 입력이 n =5와 같으면 초기 전구가 [0, 0, 0, 0, 0]이므로 출력은 2가 됩니다.

플레이어 1 이후:[1, 1, 1, 1, 1]
플레이어 2 이후:[1, 0, 1, 0, 1]
플레이어 3 이후:[1, 0, 0, 0, 1]
플레이어 4 이후:[1, 0, 0, 1, 1]
플레이어 5 이후:[1, 0, 0, 1, 0]

마지막에 2개의 조명이 ON 상태에 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

l :=0
r :=n
l <=r인 동안, do
- 중간:=l + (r - l)/2의 바닥
- mid * mid <=n <(mid + 1)^2이면
  - 중간 반환
- 그렇지 않으면 n
- r :=중간
그렇지 않으면
- l :=중간 + 1

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def solve(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

n = 5
print(solve(n))

반환