โปรแกรมนับจำนวนสวิตช์ที่จะเปิดหลังจากพลิกโดย n คนใน python

สมมติว่าเรามีตัวเลข n และมีสวิตช์ n ตัวในห้องหนึ่ง และสวิตช์ทั้งหมดปิดอยู่ ตอนนี้ n คนที่พลิกสวิตช์ดังนี้ −

• บุคคลที่ 1 พลิกสวิตช์ทั้งหมดที่เป็นทวีคูณของ 1 (ดังนั้นสวิตช์ทั้งหมด)
• คนที่ 2 พลิกสวิตช์ที่เป็นทวีคูณของ 2 (2, 4, 6, ...)
• บุคคลที่ฉันพลิกสวิตช์ที่เป็นทวีคูณของ i

เราต้องหาจำนวนสวิตซ์ที่จะเปิดตอนท้าย

ดังนั้น หากอินพุตเป็น n =5 เอาต์พุตจะเป็น 2 เนื่องจากในตอนแรกทั้งหมดปิดอยู่ [0, 0, 0, 0, 0] บุคคลที่ 1 พลิกทั้งหมด [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 +(r - l) / 2
  • ถ้า mid^2 <=n <(กลาง + 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))

อินพุต

5

ผลลัพธ์

2