Sum of Digits Problem – Dynamic Programming Solutions

«
»

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

advertisement
Expected Input and Output

Case-1:

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

Case-2:

n=9
sum=45

Case-3:

advertisement
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.

  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.

advertisement
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
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn