1부터 n까지의 모든 숫자의 자릿수 합 계산

이 문제에서는 1에서 n 사이의 모든 숫자의 자릿수의 합을 찾아야 합니다. 예를 들어 54의 자릿수의 합은 5 + 4 =9입니다. 이와 같이 모든 숫자와 자릿수의 합을 찾아야 합니다.

10 ^{d - 1} 이 있다는 것을 알고 있습니다. 자릿수가 d인 숫자를 생성할 수 있습니다. 모든 숫자 d의 합을 찾기 위해 재귀 공식을 사용할 수 있습니다.

합계(10 ^d - 1)=sum(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