Home » Algorithms

Compute sum of digits in all numbers from 1 to N for a given N

In this article, we are going to see how to compute sum of digits in all numbers from 1 to N for a given N?
Submitted by Vivek Kothari, on December 17, 2018

Problem statement: We have given a number N and we have to find out the sum of digits in all numbers from 1 to N.

Solution

Brute force approach:

Simple idea for solution is that if we get number greater than 9, i.e., the number having more than one digit, we extract every individual digit of that and sum together to find final result.

    function sum(N) //brute force approach
        sum = 0;
        for(i =1 to N)
        {
            temp = i;
            while(temp != 0)
            {
                sum = sum + temp%10;
                temp = temp/10;
            }
        }
        return sum;
    END FUNCTION

The time complexity for this solution in O(Nlog10(N)) as we have to sum N items and in worst case the number of digits a number has is log10(N).

Better approach using Dynamic Programming

Now, we figure out the solution which takes only log10(N) time. We can use dynamic programming here to find the solution which takes log10(N) time, the optimal substructure for the problem is discussed below:

Let you want to calculate sum(9999) & in order to find it you have to calculate sum(999). To calculate sum(999) you have to find out sum(99) and similarly for sum(99) you have to calculate sum(9).

sum(9999)=>sum(999)=>sum(99)=>sum(9)

sum (10 – 1) = sum(9) = 1 + 2 + 3 + 4 ... + 9 = 45
Similarly , 
sum(100 – 1) =  sum(99)  = 45 + (10 + 45) + (20 + 45) + ... (90 + 45)
            = 45*10 + (10 + 20 + .................+ 80 + 90)
            = 45*10 + 10(1 + 2 + ..................+ 8 + 9)
            = 45*10 + 10 * 45
            = sum(9)*10 + 10*45
sum(1000 – 1) = sum(999) = sum(99)*10 + 100 * 45
so, we can write recursive formula of overlapping 
sub-problems for computing sum(10d – 1) as: 
sum(10d - 1) = sum(10d-1 - 1) * 10 + 45*(10d-1)

Example explanation using DP:

Now, let’s see for N = 3266 i.e we have to find sum of digits of first 3266 numbers.

If you want to find sum for N = 3266 then we can think it like this:

Sum of numbers from (0 – 999) + from(1000 – 1999) + from(2000 – 2999) + from(3000 – 3266)
Now it can be written as :
=>sum(999)+ { sum(999) + 1 occur 1000 times } + { sum(999) + 2 occur 1000 times } + {sum(266) + 3 occur 266 times}
=>sum(999) + { sum(999) + 1 * 1000 } + { sum(999) + 2 * 1000 } + {sum(266) + 3 * 266}
=> 3 * sum(999) + (1 + 2 )*1000 + 3 * 266 + sum(266)
Now sum(266) can be written as :
=> sum(0 to 99) + sum(100 to 199) + sum(200 to 266)
=> sum(99) + { sum(99) + 1 * 100 } + { 2 * 66 + sum(66) }
=> 2 * sum(99) + 1*100 + 2 * 66 + sum(66)

Now observe the pattern here:

Algorithm: Now, see algorithm for solving above problem.

calculate_sum(d) 
{
	a[0] = 0
	a[i] = 45
	for(i=2 to d)
	{
		a[i] = a[i-1]*10 + 45*10^(i-1)
	}
}

sum_of_digits(N)
{	
	d = log(N)
	if (N<10) 
		return N*(N+1)/2
	//now calculate sum of digits from 
	//1 to 10^d-1 using calculate_sum()
	//function
	lmd = N/10^d // left most digit
	return lmd * a[d] + (lmd*(lmd-1)/2) * 10^d +
	lmd * (1+N % 10^d) + sum_of_digits(N % 10^d) 
}

Program 1: brute force approach for solving above problem

#include <bits/stdc++.h>
using namespace std;

long long sum(int N)
{ 
	long long sum = 0;
	long long i,temp;
	for(i =1;i<=N;i++)
	{
		temp = i;
		while(temp != 0)
		{
			//extracting last digit and adding to sum
			sum = sum + temp%10;
			//removing digit
			temp = temp/10;
		}
	}
	return sum;
}

int main()
{
	int N;
	
	cout<<"enter the value of N : ";
	cin>>N;
	cout << "Sum of digits of first " << N << " natural numbers is = "<<sum(N);
	
	return 0;
}

Output

enter the value of N : 450
Sum of digits of first 450 natural numbers is = 4734

Program 2: In this program we see the implementation of efficient approach

#include <bits/stdc++.h>
using namespace std; 

int a[100000];

void calculate_sum(int d) 
{
	a[0] = 0;
	a[1] = 45;
	for(int i=2;i<=d;i++)
	{
		//sum(10^d - 1) = sum((10^d-1)-1)*10 + 45 * 10^(d-1)
		a[i] = a[i-1]*10 + 45*pow(10,i-1);
	}
}

long long sum_of_digits(int N)
{
	//base condition
	//if N less than 10
	//return sum of first N numbers
	if (N<10) 
		return N*(N+1)/2;

	//calculating number of digits in N   	
	int d = log10(N);

	//calculate sum of digits from 1 to 10^d-1
	calculate_sum(d);

	//left most digit
	int lmd = N/pow(10,d);

	//store the value of 10^d
	int t = ceil(pow(10,d));

	return lmd * a[d] + (lmd*(lmd-1)/2) * t + lmd * (1 + N % t) + sum_of_digits(N % t); 
}

int main() 
{ 
	int N;
	cout<<"enter the value of N : ";
	cin>>N;
	cout << "Sum of digits of first " << N << " natural numbers is = "<<sum_of_digits(N);
	return 0;
}

Output

enter the value of N : 450
Sum of digits of first 450 natural numbers is = 4734