หาค่า N สูงสุดที่ผลรวมกำลังสอง 1 ถึง N ไม่เกิน X ใน Python

โจทย์: กำหนด X หา N สูงสุดที่ 1² + 2² + ... + N² ≤ X

สูตร: ผลรวมกำลังสอง = N(N+1)(2N+1)/6

ตัวอย่าง: X=7 → N=2 เพราะ 1²+2²=5 ≤7 แต่ 1²+2²+3²=14 >7

อัลกอริทึม Binary Search

1. low=1, high=100000 (ค่าสูงสุดที่เป็นไปได้)
2. mid = (low+high)//2
3. ถ้า sum_of_squares(mid) ≤ X → N=mid, low=mid+1
4. มิฉะนั้น high=mid-1

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

def sum_of_squares(N):
    return (N * (N + 1) * (2 * N + 1)) // 6

def get_max(X):
    low, high = 1, 100000
    N = 0
    while low <= high:
        mid = (low + high) // 2
        if sum_of_squares(mid) <= X:
            N = mid
            low = mid + 1
        else:
            high = mid - 1
    return N

print(get_max(7))  # 2

ผลลัพธ์

2

สรุป: ใช้สูตรปิดคำนวณผลรวม O(1) ร่วม Binary Search O(log X) รวม O(log X) time