Tìm N lớn nhất sao cho tổng bình phương của N số tự nhiên đầu tiên không lớn hơn X trong C ++

Khái niệm

Đối với một số nguyên X cho trước, nhiệm vụ của chúng ta là xác định giá trị lớn nhất N sao cho tổng của N số tự nhiên đầu tiên không được vượt quá X.

Đầu vào

X = 7

Đầu ra

2 là giá trị lớn nhất có thể có của N vì với N =3, tổng của chuỗi sẽ vượt quá Xi.e. 1 ^ 2 + 2 ^ 2 + 3 ^ 2 =1 + 4 + 9 =14

Đầu vào

X = 27

Đầu ra

3 là giá trị lớn nhất có thể có của N vì với N =4, tổng của chuỗi sẽ vượt quá Xi.e. 1 ^ 2 + 2 ^ 2 + 3 ^ 2 + 4 ^ 2 =1 + 4 + 9 + 16 =30

Phương pháp

Giải pháp đơn giản - Ở đây, một giải pháp đơn giản là thực hiện một vòng lặp từ 1 đến lớn nhất N sao cho S (N) ≤ X, trong trường hợp này S (N) được gọi là tổng bình phương của N số tự nhiên đầu tiên. Kết quả là tổng bình phương của N số tự nhiên đầu tiên được cho bởi công thức S (N) =N * (N + 1) * (2 * N + 1) / 6.

Cần lưu ý rằng độ phức tạp về thời gian của phương pháp này là O (N).

Phương pháp tiếp cận hiệu quả - Chúng tôi có thể triển khai một giải pháp hiệu quả khác dựa trên cách tiếp cận tìm kiếm nhị phân.

Chúng tôi làm theo thuật toán dưới đây được giải thích từng bước -

Bắt đầu tìm kiếm nhị phân trong mảng lớn hơn và lấy giá trị trung bình là (thấp + cao) / 2
Người ta thấy rằng nếu giá trị từ cả hai mảng là như nhau thì phần tử phải nằm ở phần bên phải so với dấu thấp là giữa
Dấu khác cao đến giữa vì phần tử phải ở phần bên trái của mảng lớn hơn nếu phần tử ở giữa không phải là tên.

Cần lưu ý rằng độ phức tạp về thời gian của phương pháp này là O (log N).

Ví dụ

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// Shows function to return the sum of the squares
// of first N1 natural numbers
ll squareSum(ll N1){
   ll sum1 = (ll)(N1 * (N1 + 1) * (2 * N1 + 1)) / 6;
   return sum1;
}
// Shows function to return the maximum N such that
// the sum of the squares of first N
// natural numbers is not more than 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;
}
// Driver code
int main(){
   ll X = 27;
   cout << findMaxN(X);
   return 0;
}