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 C++

Khái niệm

Cho một số nguyên X, nhiệm vụ là xác định giá trị 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.

Đầu vào

X = 7

Đầu ra

2 là giá trị N lớn nhất vì với N = 3, tổng dãy sẽ vượt quá X: 1^2 + 2^2 + 3^2 = 1 + 4 + 9 = 14

Đầu vào

X = 27

Đầu ra

3 là giá trị N lớn nhất vì với N = 4, tổng dãy sẽ vượt quá X: 1^2 + 2^2 + 3^2 + 4^2 = 1 + 4 + 9 + 16 = 30

Phương pháp

Giải pháp đơn giản - Chạy vòng lặp từ 1 đến N lớn nhất sao cho S(N) ≤ X, trong đó S(N) là tổng bình phương N số tự nhiên đầu tiên. Công thức: S(N) = N * (N + 1) * (2 * N + 1) / 6. Độ phức tạp thời gian: O(N).

Phương pháp hiệu quả - Sử dụng tìm kiếm nhị phân.

Thuật toán:

Bắt đầu tìm kiếm nhị phân, lấy mid = (low + high) / 2
Nếu giá trị từ cả hai mảng giống nhau thì phần tử phải ở phần bên phải, đặt low = mid
Ngược lại đặt high = mid vì phần tử phải ở phần bên trái nếu mid không giống nhau.

Độ phức tạp thời gian: O(log N).

Ví dụ

// C++ triển khai phương pháp
#include <bits/stdc++.h>
using namespace std;
#define ll long long

// Hàm trả về tổng bình phương N1 số tự nhiên đầu tiên
ll squareSum(ll N1){
    ll sum1 = (ll)(N1 * (N1 + 1) * (2 * N1 + 1)) / 6;
    return sum1;
}

// Hàm trả về N lớn nhất sao cho tổng bình phương không quá X
ll findMaxN(ll X){
    ll low1 = 1, high1 = 100000;
    int N1 = 0;
    while (low1 <= high1) {
        ll mid1 = (high1 + low1) / 2;
        if (squareSum(mid1) <= X) {
            N1 = mid1;
            low1 = mid1 + 1;
        }
        else
            high1 = mid1 - 1;
    }
    return N1;
}

// Chương trình chính
int main(){
    ll X = 27;
    cout << findMaxN(X);
    return 0;
}