C++에서 처음 N개의 자연수의 제곱의 합이 X보다 크지 않은 최대 N 찾기

<시간/>

컨셉

주어진 정수 X와 관련하여 우리의 임무는 처음 N개의 자연수의 합이 X를 초과하지 않도록 최대값 N을 결정하는 것입니다.

입력

X = 7

출력

N =3의 경우 계열의 합이 Xi.e를 초과하므로 2는 N의 가능한 최대 값입니다. 1^2 + 2^2 + 3^2 =1 + 4 + 9 =14

입력

X = 27

출력

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개의 자연수의 제곱의 합이라고 합니다. 그 결과 처음 N개의 자연수의 제곱합은 S(N) =N * (N + 1) * (2 * N + 1) / 6의 공식으로 주어집니다.

이 접근 방식의 시간 복잡도는 O(N)입니다.

효율적인 접근 방식 − 바이너리 검색 방식을 기반으로 하는 또 다른 효율적인 솔루션을 구현할 수 있습니다.

우리는 단계별로 설명되는 아래 알고리즘을 따릅니다 -

더 큰 배열에서 이진 검색을 시작하고 중간을 (낮음 + 높음) / 2
로 가져옵니다.
두 배열의 값이 같으면 요소가 오른쪽 부분에 있어야 합니다. somark low as 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;
}