এই সমস্যায়, আমাদের 1 থেকে n রেঞ্জের সমস্ত সংখ্যার অঙ্কের যোগফল খুঁজে বের করতে হবে। উদাহরণস্বরূপ, 54-এর অঙ্কের যোগফল হল 5 + 4 =9, এইভাবে, আমাদের সমস্ত সংখ্যা এবং তাদের অঙ্কের যোগফল খুঁজে বের করতে হবে।
আমরা জানি যে এখানে 10 d - 1 আছে সংখ্যা তৈরি করা যেতে পারে, যার সংখ্যা d। ডি ডিজিটের সেই সমস্ত সংখ্যার যোগফল বের করতে আমরা একটি পুনরাবৃত্ত সূত্র ব্যবহার করতে পারি।
যোগফল(10 d - 1) =যোগফল(10 d-1 - 1)*10+45*(10 d-1 )
ইনপুট এবং আউটপুট
Input: This algorithm takes the upper limit of the range, say it is 20. Output: Sum of digits in all numbers from 1 to n. Here the result is 102
অ্যালগরিদম
digitSumInRange(n)
ইনপুট: ব্যাপ্তির উপরের সীমা।
আউটপুট - পরিসরের সমস্ত সংখ্যার সংখ্যার যোগফল (1-n)।
Begin if n < 10, then return n(n+1)/2 digit := number of digits in number d := digit – 1 define place array of size digit place[0] := 0 place[1] := 45 for i := 2 to d, do place[i] := place[i-1]*10 + 45 * ceiling(10^(i-1)) power := ceiling(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 done End
উদাহরণ
#include<iostream>
#include<cmath>
using namespace std;
int digitSumInRange(int n) {
if (n<10)
return n*(n+1)/2; //when one digit number find sum with formula
int digit = log10(n)+1; //number of digits in number
int d = digit-1; //decrease digit count by 1
int *place = new int[d+1]; //create array to store sum upto 1 to 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)); //computing the power of 10
int msd = n/power; //find most significant digit
return msd*place[d] + (msd*(msd-1)/2)*power +
msd*(1+n%power) + digitSumInRange(n%power); //recursively find the sum
}
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
