查找最大N，以使C中的前N个自然数的平方和不超过X

概念

对于给定的整数X，我们的任务是确定最大值N，以使前N个自然数的总和不超过X。

输入值

X = 7

输出结果

2是N的最大可能值，因为对于N = 3，级数之和将超过X，即1 ^ 2 + 2 ^ 2 + 3 ^ 2 = 1 + 4 + 9 = 14

输入值

X = 27

输出结果

3是N的最大可能值，因为对于N = 4，级数之和将超过X，即1 ^ 2 + 2 ^ 2 + 3 ^ 2 + 4 ^ 2 = 1 + 4 + 9 + 16 = 30

方法

简单的解决方案-这里，一个简单的解决方案是执行从1到最大N的循环，以使S(N)≤X，在这种情况下，S(N)被称为前N个自然数的平方和。结果，前N个自然数的平方和由公式S(N)= N *（N + 1）*（2 * N + 1）/ 6给出。

应该注意的是，这种方法的时间复杂度是O(N)。

高效的方法-我们可以基于二进制搜索方法实现另一种高效的解决方案。

我们遵循以下算法，逐步解释-

在更大的数组中开始二进制搜索，并以（low + high）/ 2作为中间值
已经看到，如果两个数组中的值相同，则元素必须在右侧，因此将低标记为中
如果中部元素不同，则元素中高的其他标记必须位于较大数组的左侧。

应该注意的是，这种方法的时间复杂度为O（log N）。

示例

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long
//显示函数以返回平方和
//第一个N1自然数
ll squareSum(ll N1){
   ll sum1 = (ll)(N1 * (N1 + 1) * (2 * N1 + 1)) / 6;
   return sum1;
}
//显示函数以返回最大N，例如
//第一个N的平方和
//自然数不超过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;
}
//驱动程式码
int main(){
   ll X = 27;
   cout << findMaxN(X);
   return 0;
}

输出结果

基础教程