Sum of Digits Problem using Dynamic Programming

This is a C++ Program that Solves Sum of Digits Problem using Dynamic Programming technique.

Problem Description

Given a number n, find the sum of digits of all numbers from 1 to n.

Problem Solution

To solve this problem in an efficient manner, we will calculate the sum in a pattern. If we are given a number 8459, we will calculate the result in this manner –
(8*999) + ((7*8)/2)*1000 + 8*459 + 459

Expected Input and Output

Case-1:

n=5
sum =15 (1+2+3+4+5)

Case-2:

advertisement
n=9
sum=45

Case-3:

n=10
sum=46 (notice that the contribution of the number 10 in the sum is  just 1 not 10)
Program/Source Code

Here is source code of the C++ Program to Solve Sum of Digits Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

Free 30-Day Java Certification Bootcamp is Live. Join Now!
  1. #include<iostream>
  2. #include<cmath>
  3. using namespace std;
  4.  
  5. //this function calculates the sum of digits of numbers from 1 to 10^digits -1
  6. //if digits=2, sum of 1 to 99
  7. int sumXminusOne(int digits)
  8. {
  9.     int sum=0;
  10.  
  11.     for(int i=1;i<=digits;i++)
  12.     {
  13.         //45 is the sum of digits of numbers from 1...9
  14.         sum=sum*10 + 45*pow(10,i-1);
  15.     }
  16.  
  17.     return sum;
  18. }
  19.  
  20.  
  21. //function to return sum of digits of all numbers from 1 to n
  22. int sumDigits(int n)
  23. {
  24.     if(n<10)
  25.         return n*(n+1)/2;
  26.  
  27.     //digits is equal to number of digits in n minus one
  28.     int digits;
  29.     digits=log10(n);
  30.  
  31.     int X=pow(10,digits);
  32.  
  33.     //leftmost digit of the number
  34.     int left=n/X;
  35.  
  36.     //sum of digits of all numbers form 1 to n
  37.     int sum=left*sumXminusOne(digits) +  
  38.             ((left*(left-1))/2)*X +
  39.             left*(n%X +1) +
  40.             sumDigits(n%X);
  41.  
  42.     return sum;
  43.  
  44. }
  45.  
  46. int main()
  47. {
  48.     int n;
  49.  
  50.     cout<<"Enter the number "<<endl;
  51.     cin>>n;
  52.  
  53.     cout<<"The sum of digits of all numbers from 1 to "<<n<<" is "<<endl;
  54.     cout<<sumDigits(n);
  55.  
  56.     cout<<endl;
  57.     return 0;
  58. }
Program Explanation

In the main function, we take input for the value n and pass this value to the function sumDigits. This function will return the sum of digits of all integers from 1 to n to be displayed on the standard output.

Runtime Test Cases
 
Case-1:
$ g++ sum_digits.cpp 
$ ./a.out
Enter the number 
45
The sum of digits of all numbers from 1 to 45 is 
279

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

advertisement

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
I’m Manish - Founder and CTO at Sanfoundry. I’ve been working in tech for over 25 years, with deep focus on Linux kernel, SAN technologies, Advanced C, Full Stack and Scalable website designs.

You can connect with me on LinkedIn, watch my Youtube Masterclasses, or join my Telegram tech discussions.

If you’re in your 40s–60s and exploring new directions in your career, I also offer mentoring. Learn more here.