Numbers (Editorial)

Solution

General Idea :

We are given two integers $a$ and $b$ (a \le b), and we must compute the sum of all digits of all numbers written from $a$ to $b$ inclusive.

Since a, b \le 10^{12}, a direct loop is impossible. We instead compute:

[ Answer = S(b) - S(a-1) ]

where $S(x)$ is the sum of digits of all numbers from $0$ to $x$.

—

Digit DP Formula for $S(n)$ :

Let $n$ be represented as digits. For each digit position with factor p = 10^i:

[ higher = np 10 ] [ current = ( np ) 10 ] [ lower = n p ]

The contribution of this digit position to the total sum is:

[ higher 45 p + current(current-1)2 p + current (lower + 1) ]

Summing this over all positions gives $S(n)$.

—

Final Formula :

[ Answer = S(b) - S(a-1) ]

—

Time Complexity: [ O(_10 n) ]

—

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

ll sumDigits(ll n) {
    if (n < 0) return 0;
    ll res = 0;
    for (ll p = 1; p <= n; p *= 10) {
        ll higher = n / (p * 10);
        ll current = (n / p) % 10;
        ll lower = n % p;

        res += higher * 45 * p;
        res += (current * (current - 1) / 2) * p;
        res += current * (lower + 1);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll a, b;
    cin >> a >> b;

    cout << sumDigits(b) - sumDigits(a - 1);
    return 0;
}