Python - นับจำนวนไฟที่เปิดหลังจาก n คนสลับสวิตช์

โจทย์: มี n สวิตช์และ n คน คนที่ i จะสลับสวิตช์ที่เป็นจำนวนคูณของ i (i, 2i, 3i, ...) หาจำนวนสวิตช์ที่เปิดอยู่ (ON) ท้ายสุด

ตัวอย่าง

Input: n = 5
Output: 2
สวิตช์เริ่มทั้งหมด OFF [0,0,0,0,0]:

• คน 1: สลับทุกตัว → [1,1,1,1,1]
• คน 2: สลับ 2,4 → [1,0,1,0,1]
• คน 3: สลับ 3 → [1,0,0,0,1]
• คน 4: สลับ 4 → [1,0,0,1,1]
• คน 5: สลับ 5 → [1,0,0,1,0]

ข้อสังเกตสำคัญ: Perfect Squares

สวิตช์ k จะถูกสลับจำนวนครั้งเท่ากับ จำนวนตัวหารของ k
- ตัวหารส่วนใหญ่มาคู่กัน (เช่น 12: 1×12, 2×6, 3×4) → จำนวนคู่ → สลับคู่ → กลับเป็น OFF
- ยกเว้น Perfect Square (เช่น 16: 1×16, 2×8, 4×4) → ตัวหารกลางซ้ำ → จำนวนคี่ → คงเป็น ON

ดังนั้น คำตอบ = จำนวน Perfect Square ≤ n = ⌊√n⌋

อัลกอริทึม: 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

# ทดสอบ
n = 5
print(solve(n))  # Output: 2 (1²=1, 2²=4 ≤ 5, 3²=9 > 5)

วิธีง่ายกว่า (Math)

import math

def solve_simple(n):
    return int(math.isqrt(n))  # Python 3.8+
    # หรือ int(math.sqrt(n)) สำหรับ Python เก่า

print(solve_simple(5))    # 2
print(solve_simple(100))  # 10
print(solve_simple(1000)) # 31

ความซับซ้อน

• Binary Search: O(log n) Time, O(1) Space
• Math sqrt: O(1) Time, O(1) Space

การทดสอบเพิ่มเติม

for n in [1, 2, 3, 4, 5, 10, 16, 100, 1000]:
    print(f"n={n}: {solve(n)} lights ON")

Output: n=1: 1, n=2: 1, n=3: 1, n=4: 2, n=5: 2, n=10: 3, n=16: 4, n=100: 10, n=1000: 31