এই সমস্যায়, আমাদের একটি পূর্ণসংখ্যার মান দেওয়া হয়েছে। আমাদের কাজ হল n পদ পর্যন্ত n^2 - (n-1)^2-এর সমষ্টি খুঁজে বের করা .
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input : N = 3 Output : 6
ব্যাখ্যা −
[12 - (0)2] + [22 - (1)2] + [32 - (2)2] = 1 - 0 + 4 - 1 + 9 - 2 = 9
সমাধান পদ্ধতি
সমস্যা সমাধানের একটি সহজ পদ্ধতি হল সিরিজের সাধারণ পদ খুঁজে বের করা এবং তারপর n পদ পর্যন্ত যোগফল খুঁজে বের করা। এবং সূত্র ব্যবহার করে যোগফল গণনা করলে O(1) সময় কমে যাবে। এছাড়াও, ফলাফল বিশাল হতে পারে তাই মানগুলির মডুলাস খুঁজে বের করতে হবে৷
চলুন সিরিজের nম মেয়াদের সূত্রটি বের করা যাক,
$T_{n}\:=\:\mathrm{n^2-(n-1)^2}$
a2 - b2 সূত্র ব্যবহার করে সমাধান করার সময়,
$T_{n}\:=\:\mathrm{(n+n-1)*(n-n+1)}$
$=\:\mathrm{(2*n-1)*(1)}$
$=\:\mathrm{2*n-1}$
এটি ব্যবহার করে আমরা সিরিজের n পদ পর্যন্ত যোগফল খুঁজে পেতে পারি,
$\mathrm{sum}\:=\:\sum(2*n-1)$
$\mathrm{sum}\:=\:2*\sum{n}\:-\:\sum{1}$
$\mathrm{sum}\:=\:2*(n*(n+1))/2-n$
$\mathrm{sum}\:=\:n*(n+1)-n\:=\:n^2\:+\:n\:-\:n\:=\:n^2$
সিরিজের যোগফল হল n 2 যা একটি বড় সংখ্যা, তাই মোড নেওয়া হবে।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include<iostream> using namespace std; #define mod 1000000007 long long calcSumNTerms(long long n) { return ((n%mod)*(n%mod))%mod; } int main() { long long n = 4325353; cout<<"The sum of series upto n terms is "<<calcSumNTerms(n); return 0; }
আউটপুট
The sum of series upto n terms is 678443653