Tính tổng các chữ số trong tất cả các số từ 1 đến n

Trong bài toán này, chúng ta phải tìm tổng các chữ số của tất cả các số trong phạm vi từ 1 đến n. Ví dụ, tổng các chữ số của 54 là 5 + 4 =9, Như thế này, chúng ta phải tìm tất cả các số và tổng các chữ số của chúng.

Chúng tôi biết rằng có 10 ^{d - 1} số có thể được tạo ra, có số chữ số là d. Để tìm tổng của tất cả các số đó có chữ số d, chúng ta có thể sử dụng công thức đệ quy.

sum (10 ^d - 1) =sum (10 ^d-1 - 1) * 10 + 45 * (10 ^d-1 )

Đầu vào và Đầu ra

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

Thuật toán

digitSumInRange(n)

Đầu vào: Giới hạn trên của phạm vi.

Đầu ra - tổng các chữ số cho tất cả các số trong phạm vi (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

Ví dụ

#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);
}

Đầu ra

Enter upper limit of the range: 20
Sum of digits in range (1 to 20) is: 102