最初のN個の自然数の2乗の合計がC++でX以下になるように最大Nを見つけます

コンセプト

与えられた整数Xに関して、私たちのタスクは、最初のN個の自然数の合計がXを超えないように最大値Nを決定することです。

入力

X = 7

出力

2

N =3の場合、級数の合計がXi.eを超えるため、2はNの可能な最大値です。 1 ^ 2 + 2 ^ 2 + 3 ^ 2 =1 + 4 + 9 =14

入力

X = 27

出力

3

N =4の場合、級数の合計がXi.eを超えるため、3はNの可能な最大値です。 1 ^ 2 + 2 ^ 2 + 3 ^ 2 + 4 ^ 2 =1 + 4 + 9 + 16 =30

メソッド

簡単な解決策 −ここで、簡単な解決策は、S（N）≤Xになるように1から最大Nまでループを実行することです。この場合、S（N）は最初のN個の自然数の2乗の合計と呼ばれます。この結果、最初のN個の自然数の2乗の合計は、式S（N）=N *（N + 1）*（2 * N + 1）/6で与えられます。

このアプローチの時間計算量はO（N）であることに注意してください。

効率的なアプローチ −二分探索アプローチに基づく別の効率的なソリューションを実装できます。

ステップバイステップで説明されている以下のアルゴリズムに従います-

• より大きな配列で二分探索を開始し、（低+高）/ 2

  として中程度になります

• 両方の配列の値が同じである場合、要素は右側にある必要があります。

• それ以外の場合、中央の要素が同じでない場合は、要素が大きな配列の左側にある必要があるため、中央の高さをマークします。

このアプローチの時間計算量はO（log N）であることに注意してください。

例

// 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;
}

出力

3