Pythonでn人が切り替えた後にオンになるスイッチの数をカウントするプログラム

番号がnで、部屋にn個のスイッチがあり、すべてのスイッチがオフになっているとします。今、次のようにスイッチを切り替えるn人-

• 人1は、1の倍数であるすべてのスイッチを切り替えます（つまり、すべてのスイッチを切り替えます）。
• Person 2は、2の倍数（2、4、6、...）のスイッチを切り替えます
• Person iは、iの倍数であるスイッチを切り替えます。

最後にオンになるスイッチの数を見つける必要があります。

したがって、入力がn =5の場合、出力は2になります。最初はすべてがオフであり、[0、0、0、0、0]、人物1はすべてを反転します[1、1、1、1、1] 、Person 2は[1、0、1、0、1]のように反転し、次にPerson 3は[1、0、0、0、0]を実行し、Person 4は[1、0、0、1、0]を実行しました

これを解決するには、次の手順に従います-

• l：=0、r：=n
• l <=rの場合、do
  • mid：=l +（r --l）/ 2
  • mid ^ 2 <=n <（mid + 1）^ 2の場合、
    • 途中で戻る
  • それ以外の場合、n
  • r：=mid
• それ以外の場合、
  • l：=mid + 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))

入力

5

出力

2