Chương trình đếm số công tắc bật sau khi n người lật theo quy luật bằng Python

Có n công tắc ban đầu tắt. Người thứ i lật các công tắc bội số của i. Tìm số công tắc bật cuối cùng.

Ví dụ: n=5 → 2 công tắc bật (1 và 4).

Giải thuật

Chỉ các công tắc ở vị trí số chính phương mới bị lật số lần lẻ → bật. Số lượng số chính phương ≤ n là floor(sqrt(n)). Sử dụng tìm kiếm nhị phân để tìm căn bậc hai nguyên lớn nhất không vượt quá n.

Ví dụ minh họa

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))

Đầu vào

5

Đầu ra

2