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

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

Ta biết rằng có 10^(d-1) số có thể tạo ra, có số chữ số là d. Để tìm tổng của tất cả những số có chữ số d, ta có thể 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

Đầu vào: Thuật toán này nhận giới hạn trên của phạm vi, ví dụ là 20.
Đầu ra: Tổng chữ số trong tất cả số từ 1 đến n. Ở đây kết quả là 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 chữ số cho tất cả số trong phạm vi (1-n).
Bắt đầu
  nếu n < 10 thì
    trả về n(n+1)/2
  digit := số chữ số trong số
  d := digit - 1
  định nghĩa mảng place kích thước digit
  place[0] := 0
  place[1] := 45
  với i := 2 đến d, làm
    place[i] := place[i-1]*10 + 45 * ceiling(10^(i-1))
  kết thúc
  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)
  trả về res
Kết thúc

Ví dụ (C++)

#include <iostream>
#include <cmath>
using namespace std;

int digitSumInRange(int n) {
  if (n < 10)
    return n*(n+1)/2; // khi số 1 chữ số, tìm tổng bằng công thức
  
  int digit = log10(n) + 1; // số chữ số trong số
  int d = digit - 1; // giảm số chữ số đi 1
  
  int *place = new int[d+1]; // tạo mảng lưu tổng đến 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)); // tính lũy thừa 10
  int msd = n/power; // tìm chữ số quan trọng nhất (most significant digit)
  
  return msd*place[d] + (msd*(msd-1)/2)*power +
         msd*(1 + n%power) + digitSumInRange(n%power);
  // đệ quy tìm tổng
}

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