在 C++ 中查找最大的 N,使得前 N 个自然数的平方和不大于 X


概念

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

输入

X = 7

输出

2

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

输入

X = 27

输出

3

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

  • 如果两个数组的值相同,则元素必须在右侧,因此将 low 设为 mid

  • 否则,如果中间元素不相等,则将 high 设为 mid,因为元素必须在较大数组的左侧。

需要注意的是,这种方法的时间复杂度为 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

更新于:2020年7月25日

345 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告