এই সমস্যায়, আমাদের ১ থেকে n পরিসরের সব সংখ্যার ডিজিটের যোগফল বের করতে হবে। উদাহরণস্বরূপ, ৫৪-এর ডিজিটের যোগফল ৫ + ৪ = ৯, এইভাবে সব সংখ্যার ডিজিটের যোগফল বের করতে হবে।
আমরা জানি, d সংখ্যক ডিজিট দিয়ে 10^(d-1) সংখ্যা তৈরি করা যায়। d ডিজিটের সব সংখ্যার যোগফল বের করতে একটি রিকারসিভ ফর্মুলা ব্যবহার করা যায়।
sum(10^d - 1) = sum(10^(d-1) - 1) * 10 + 45 * (10^(d-1))
ইনপুট এবং আউটপুট
ইনপুট: এই অ্যালগরিদম পরিসরের উপরের সীমা নেয়, ধরি সেটি ২০। আউটপুট: ১ থেকে n পর্যন্ত সব সংখ্যার ডিজিটের যোগফল। এখানে ফলাফল ১০২।
এলগরিদম
digitSumInRange(n)
ইনপুট: পরিসরের উপরের সীমা।
আউটপুট: পরিসর (১-n) এর সব সংখ্যার ডিজিটের যোগফল।
শুরু
যদি n < 10, তবে
return n(n+1)/2
digit := সংখ্যার ডিজিট সংখ্যা
d := digit - 1
place অ্যারে সংজ্ঞায়িত করুন digit আকারের
place[0] := 0
place[1] := 45
i := 2 থেকে d পর্যন্ত, করুন
place[i] := place[i-1]*10 + 45 * ceil(10^(i-1))
শেষ লুপ
power := ceil(10^d)
msd := n/power
res := msd*place[d] + (msd*(msd-1)/2)*power +
msd*(1 + n mod power) + digitSumInRange(n mod power)
return res
শেষ
উদাহরণ (C++ কোড)
#include <iostream>
#include <cmath>
using namespace std;
int digitSumInRange(int n) {
if (n < 10)
return n*(n+1)/2; // এক ডিজিট সংখ্যা হলে ফর্মুলা দিয়ে যোগফল বের করুন
int digit = log10(n) + 1; // সংখ্যার ডিজিট সংখ্যা
int d = digit - 1; // ডিজিট কাউন্ট ১ কমান
int *place = new int[d+1]; // ১ থেকে 10^place[i] পর্যন্ত যোগফল স্টোর করার অ্যারে
place[0] = 0;
place[1] = 45;
for (int i = 2; i <= d; i++)
place[i] = place[i-1]*10 + 45*ceil(pow(10, i-1));
int power = ceil(pow(10, d)); // ১০-এর ঘাত গণনা
int msd = n/power; // সবচেয়ে উল্লেখযোগ্য ডিজিট (MSD) বের করুন
return msd*place[d] + (msd*(msd-1)/2)*power +
msd*(1 + n%power) + digitSumInRange(n%power); // রিকারসিভভাবে যোগফল বের করুন
}
int main() {
int n;
cout << "Enter upper limit of the range: "; cin >> n;
cout << "Sum of digits in range (1 to " << n << ") is: " << digitSumInRange(n);
}
আউটপুট
Enter upper limit of the range: 20 Sum of digits in range (1 to 20) is: 102
