# 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

Expected Input and Output

Case-1:

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

Case-2:

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

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. 