This is a C++ Program that Solves Sum of Digits Problem using Dynamic Programming technique.
Given a number n, find the sum of digits of all numbers from 1 to n.
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
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)
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;
}
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.
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.
- Get Free Certificate of Merit in Data Structure I
- Participate in Data Structure I Certification Contest
- Become a Top Ranker in Data Structure I
- Take Data Structure I Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Practice Design & Analysis of Algorithms MCQ
- Apply for Information Technology Internship
- Apply for Computer Science Internship
- Practice Programming MCQs
- Buy Computer Science Books