在 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
广告