Compute sum of digits in all numbers from 1 to n

December 7, 2021

Compute the sum of digits in all numbers from 1 to n

In compute sum of digits problem we have to compute the total digit sum of all numbers from 1 to n. The problem can be solved using dynamic programming. In this article, we will explain the dynamic programming solution with C++ code.

Compute the sum of digits Problem Description

Given an integer n. Compute the total sum of digits of all numbers between 1 to n.

Input:

First-line contains integer n.

Output:

Single Integer, the required sum.

Example –

Input

Output

Explanation –

1+2+3+4+5+6+7+8+9+(1+0) = 46

Compute the sum of digits Problem Solution

The idea in dynamic programming questions involving digits is to breakdown the problem recursively.

Points to remember –

For each digit we have maximum 10 choices (0 to 9).
We have to generate numbers less than or equal to n.

Let’s say function f(pos) generates all numbers <= n. For each position, we will put all numbers from 0 to 9 and call to the next position. But we have to ensure that numbers stay below n. For this, we introduce another boolean variable. Our function definition becomes f(pos,flag). The flag variable is used to ensure that numbers stay below n.

If the flag is true => we can set the maximum digit at position pos equal to the digit at position pos in the number n.
If the flag is false => we can set the maximum digit at position pos equal to 9.

Time Complexity – O(d) where d number of digits in n.

Space Complexity – O(d) where d number of digits in n.

Code

#include <bits/stdc++.h>
using namespace std;
string s;
pair<int, int> dp[10][2];

/*
    return a pair 
    pair.first => sum
    pair.second=> count of numbers
*/
pair<int, int> sum(int pos, bool flag)
{
    pair<int, int> res;
    res.first = 0;
    res.second = 0;

    if (pos == s.length()) // base case we no more positions left
    {
        res.second = 1;
        return res;
    }

    if (dp[pos][flag].first != –1)
        return dp[pos][flag];

    // Getting ed digit from 0 to 9 that can be filled
    int ed = (flag) ? (s[pos] – ‘0’) : 9;

    for (int i = 0; i <= ed; i++)
    {
        pair<int, int> p = sum(pos + 1, flag & (i == ed));

        // i will we at pos position int p.second numbers
        res.first += (i * p.second + p.first);
        res.second += p.second;
    }
    return dp[pos][flag] = res;
}
int main()
{
    int n;
    cin >> n;
    s = to_string(n);
    memset(dp, –1, sizeof dp);
    cout << sum(0, 1).first << endl;
}

Output

10
46