ในปัญหานี้ เราได้รับค่าจำนวนเต็ม 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{Sum}\:=\:1/9^{*}\lbrace1^*10^1\:+\:2^*10^2\:+\:3^*10^3\:+ \:\dotsm+n^*10^n\:-\:(1+2+3+\dotsm\:n)\rbrace$
$\mathrm{Sum}\:=\:1/9^{*}\lbrace(1^*10^1\:+\:2^*10^2\:+\:3^*10^3\ :+\:\dotsm+n^*10^n)\:-\:1/2(n^*(n+1))\rbrace$
ระยะ (1*10 1 + 2*10 2 + 3*10 3 + ... + n * 10 น ) สามารถแก้ไขได้โดยแยกความแตกต่างของสูตรทั่วไปสำหรับอนุกรม
1 + x + x 2 + x 3 + ... n * x n
ดังนั้น เงื่อนไข (1 * 10 1 + 2 * 10 2 + 3 * 10 3 + ... + 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}*\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
