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.

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

//this function calculates the sum of digits of numbers from 1 to 10^digits -1

```
//if digits=2, sum of 1 to 99
```
```
int sumXminusOne(int digits)
```
```
{
```
```
    int sum=0;
```
```
 
```
```
    for(int i=1;i<=digits;i++)
```
```
    {
```

        //45 is the sum of digits of numbers from 1...9

```
        sum=sum*10 + 45*pow(10,i-1);
```
```
    }
```
```
 
```
```
    return sum;
```
```
}
```
```
 
```
```
 
```

//function to return sum of digits of all numbers from 1 to n

```
int sumDigits(int n)
```
```
{
```
```
    if(n<10)
```
```
        return n*(n+1)/2;
```
```
 
```

    //digits is equal to number of digits in n minus one

```
    int digits;
```
```
    digits=log10(n);
```
```
 
```
```
    int X=pow(10,digits);
```
```
 
```
```
    //leftmost digit of the number
```
```
    int left=n/X;
```
```
 
```

    //sum of digits of all numbers form 1 to n

    int sum=left*sumXminusOne(digits) +

```
            ((left*(left-1))/2)*X +
```
```
            left*(n%X +1) +
```
```
            sumDigits(n%X);
```
```
 
```
```
    return sum;
```
```
 
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int n;
```
```
 
```
```
    cout<<"Enter the number "<<endl;
```
```
    cin>>n;
```
```
 
```

    cout<<"The sum of digits of all numbers from 1 to "<<n<<" is "<<endl;

```
    cout<<sumDigits(n);
```
```
 
```
```
    cout<<endl;
```
```
    return 0;
```
```
}
```

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.

« Prev Page - Minimum number of Squares Problem – Dynamic Programming Solutions

» Next Page - Longest Palindromic Subsequence Problem – Dynamic Programming Solutions

Deep Dive @ Sanfoundry: