คำนวณผลรวมตัวเลขของทุกตัวเลข 1 ถึง n (Sum of Digits from 1 to n)

หาผลรวมของตัวเลขแต่ละหลักของทุกตัวเลขในช่วง 1 ถึง n เช่น 54 → 5+4=9 ต้องการผลรวมทั้งหมด

ใช้สูตรเรียกซ้ำ: sum(10^d - 1) = sum(10^(d-1) - 1) × 10 + 45 × 10^(d-1)

การรับค่าและแสดงผล

Input: ขอบเขตบน = 20
Output: Sum of digits in range (1 to 20) is: 102

อัลกอริทึม

digitSumInRange(n)

Begin
  if n < 10 then return n(n+1)/2
  
  digit := จำนวนหลักของ n
  d := digit - 1
  
  สร้างอาร์เรย์ place ขนาด digit
  place[0] := 0, place[1] := 45
  for i := 2 ถึง d do
    place[i] := place[i-1]*10 + 45 * 10^(i-1)
  done
  
  power := 10^d
  msd := n / power  // หลักสำคัญที่สุด
  
  res := msd * place[d] + (msd*(msd-1)/2) * power + 
         msd * (1 + n % power) + digitSumInRange(n % power)
  
  return res
End

ตัวอย่างโค้ด (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];
  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;
  
  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