C++에서 시리즈 1+22+333+4444+... 최대 n항의 합 찾기

<시간/>

이 문제에서 정수 값 N이 주어집니다. 우리의 임무는 시리즈 1 + 22 + 333 + 4444 + 55555... 최대 n항의 합을 찾는 것입니다. .

문제를 이해하기 위해 예를 들어 보겠습니다.

Input : N = 4
Output : 4800

설명 -

1 + 22 + 333 + 4444 = 4800

솔루션 접근 방식

문제를 해결하는 간단한 방법은 급수의 일반항을 찾은 다음 n항까지 합을 찾는 것입니다. 그리고 공식을 사용하여 합계를 계산하면 시간이 O(1)로 단축됩니다.

시리즈는,

1 + 22 + 333 + 4444 + 55555...

시리즈의 합은 다음과 같이 다시 쓸 수 있습니다.

$\mathrm{Sum}\:=\:1^*(\frac{10^1-1}{9})\:+\:2^*(\frac{10^1-1}{9}) \:+\:3^*(\frac{10^1-1}{9})\dotsm$

1/9을 공통으로 취하면 합계가 됩니다.

$\mathrm{Sum}\:=\:1/9^*\lbrace(1^*10^1-1)\:+\:(2^*10^2-1)\:+\:(3 ^*10^3-1)\:+\:\dotsm(n^*10^1-n)\rbrace$

$\mathrm{합}\:=\:1/9^{*}\lbrace1^*10^1\:+\:2^*10^2\:+\:3^*10^3\:+ \:\dotsm+n^*10^n\:-\:(1+2+3+\dotsm\:n)\rbrace$

$\mathrm{합}\:=\:1/9^{*}\lbrace(1^*10^1\:+\:2^*10^2\:+\:3^*10^3\ :+\:\dotsm+n^*10^n)\:-\:1/2(n^*(n+1))\rbrace$

용어(1*10¹ + 2*10² + 3*10³ + ... + n^* 10ⁿ ) 급수에 대한 일반 공식을 미분하여 풀 수 있습니다.

1 + x + x² + x³ + ... n^* xⁿ

따라서 항(1^* 10¹ + 2^* 10² + 3^* 10³ + ... + n^* 10ⁿ )는 다음과 같이 다시 쓸 수 있습니다.

$\frac{n^*(10^{n+2})-(n+1)*(10^{n+1})+10}{81}$

합계 공식을 다시 대입하면

$\mathrm{Sum}\:=\:1/9^*\lbrace(\frac{n^*(10^{n+2})-(n+1)*(10^{n+1}) +10)}{81}\:-\:1/2(n^*(n+1))\rbrace$

$\mathrm{Sum}\:=\:\frac{1}{1458}*\lbrace2^*(n*(10^{n+2})-(n+1)*(10^{n+1) })+10)-81^*n^*(n+1)\rbrace$

$\mathrm{Sum}\:=\:\frac{1}{1458}*\lbrace(n^*(2^*10^{n+1}-2^*10^{n+1})- 2^*10^{n+1})\:+\:20\:-\:81^*n^2-81n\rbrace$

$\mathrm{Sum}\:=\:\frac{1}{1458}*\lbrace10^{n+1*}(20n-2n-2)-81n^2-81n+20\rbrace$

$\mathrm{Sum}\:=\:\frac{1}{1458}*\lbrace10^{n+1*}(18n-2)-81n^2-81n+20\rbrace$

예시

솔루션 작동을 설명하는 프로그램

#include<iostream>
#include<math.h>
using namespace std;
int calcSumNTerms(int n) {
   return ( ( (18*n - 2)*(pow(10, n+1)) - 81*n*n - 81*n + 20 )/1458 );
}
int main() {
   int n = 5;
   cout<<"The sum of series upto n terms is "<<calcSumNTerms(n);
   return 0;
}

출력

The sum of series upto n terms is 60355