Python - Đếm số đèn bật sau khi n người lật công tắc

Có n công tắc (khởi tạo tắt) và n người. 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ụ

Input: n = 5
Output: 2
Quá trình:

• Ban đầu: [0,0,0,0,0]
• Người 1: [1,1,1,1,1]
• Người 2: [1,0,1,0,1]
• Người 3: [1,0,0,0,1]
• Người 4: [1,0,0,1,1]
• Người 5: [1,0,0,1,0] → 2 đèn bật

Quan sát toán học

Công tắc k bị lật số lần = số ước của k. Chỉ số có số ước lẻ (số chính phương) mới bật. Số chính phương ≤ n là ⌊√n⌋.

Thuật toán: Tìm căn bậc hai nguyên bằng Binary Search

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

# Test
n = 5
print(solve(n))  # Output: 2

Cách đơn giản hơn

import math
def solve(n):
    return int(math.isqrt(n))  # Python 3.8+
    # hoặc: return int(math.sqrt(n))

Phân tích độ phức tạp

• Binary Search: O(log n)
• math.isqrt: O(1) (thuật toán phần cứng/phần mềm tối ưu)

Bài toán kinh điển: "100 doors problem" / "Bulb Switcher" (LeetCode 319).