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

มี n สวิตช์ ปิดทั้งหมด คนที่ i สลับสวิตช์ที่เป็นจำนวนคูณของ i หาจำนวนสวิตช์ที่เปิดอยู่ท้ายสุด

เช่น n=5 ให้ 2 เพราะสวิตช์ 1 และ 4 เปิดอยู่ (ตัวเลขที่มีจำนวน 약수 เป็นคี่ คือ ตัวเลขยกกำลังสอง)

ขั้นตอนการแก้ปัญหา

• โจทย์นี้เทียบเท่ากับการหาจำนวนจำนวนยกกำลังสอง ≤ n
• ใช้ Binary Search หาค่า mid ที่ mid^2 ≤ n < (mid+1)^2
• คืนค่า mid

ตัวอย่างโค้ด

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