Tìm N lớn nhất sao cho tổng bình phương N số tự nhiên đầu tiên không vượt quá X trong Python

Cho số nguyên X, tìm N lớn nhất sao cho tổng bình phương N số tự nhiên đầu tiên ≤ X.

Ví dụ: X = 7 → N = 2 vì 1²+2²=5 ≤ 7, nhưng 1²+2²+3²=14 > 7.

Thuật toán Binary Search

1. Công thức tổng bình phương: S(N) = N(N+1)(2N+1)/6.
2. Binary search trên N ∈ [1, 100000].
3. Nếu S(mid) ≤ X: cập nhật N = mid, tìm bên phải (low = mid + 1).
4. Ngược lại: tìm bên trái (high = mid - 1).

Ví dụ code

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 = (high + low) // 2
        if sum_of_squares(mid) <= X:
            N = mid
            low = mid + 1
        else:
            high = mid - 1
    return N

X = 7
print(get_max(X))

Input

7

Output

2