Interesting Function -- CF 1538F

Difficulty: 1800 * Techniques: digit decomposition, floor-division counting, math Problem Link

Quick Revisit

• PROBLEM: Count total digit changes when incrementing a counter from l to r
• KEY INSIGHT: Each digit position k changes floor(r/10^k) - floor(l/10^k) times. Sum over all positions.
• TECHNIQUES: per-digit decomposition, floor-division counting, linearity of counting
• TRANSFER: "Count total X across a range" -- decompose per position/digit before reaching for DP.

First Read

Define $f(l,r)$ as the total number of digit changes across all digit positions when you increment a counter from $l$ to $r$, one step at a time. For example, going from 9 to 10 changes two digits (units and tens). Find $f(l,r)$.

Constraints: $l,r\le {10}^9$, up to ${10}^4$ queries. So we need $O(\log )$ per query.

The Digit DP Trap

My first thought: "Digit changes... must be digit DP." I started thinking about states -- current position, tight constraint, carry propagation. Got 5 minutes in and the state space was growing. Carry propagation across digits is annoying.

Then I stopped. Let me think about what $f$ actually counts.

Counting Digit Changes Per Position

When you increment from $l$ to $r$ (that's $r-l$ increments), the ones digit changes every single time. That's $r-l$ changes for the ones digit.

The tens digit changes once every 10 increments. How many times does it change between $l$ and $r$? It's $\lfloor r/10\rfloor -\lfloor l/10\rfloor$.

The hundreds digit? $\lfloor r/100\rfloor -\lfloor l/100\rfloor$.

In general, position $k$ (counting from 0) changes $\lfloor r/{10}^k\rfloor -\lfloor l/{10}^k\rfloor$ times.

So:

$$f(l,r)=\sum _{k=0}^9(\lfloor r/{10}^k\rfloor -\lfloor l/{10}^k\rfloor )$$

That's... just arithmetic. No DP, no complicated logic.

Why This Works

Think about position $k$. It changes whenever the number crosses a multiple of ${10}^k$. Between $l$ and $r$, the number of multiples of ${10}^k$ that are crossed is exactly $\lfloor r/{10}^k\rfloor -\lfloor l/{10}^k\rfloor$.

When I realized this, I actually laughed. I'd been mentally constructing a digit DP with carry states, and the answer was a three-line loop.

The Gotcha I Almost Missed

Wait -- is the ones digit formula right? Going from $l$ to $r$ is $r-l$ increments, and the ones digit changes each time. And $\lfloor r/1\rfloor -\lfloor l/1\rfloor =r-l$. Yes, it checks out.

Another sanity check: $f(9,10)$. Ones digit changes once (9->0). Tens digit changes once (0->1). Total: 2. Formula: $(10-9)+(1-0)=1+1=2$. OK

One more: $f(99,100)$. Three digit changes. Formula: $(100-99)+(10-9)+(1-0)=1+1+1=3$. OK

The Code

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

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        long long l, r;
        scanf("%lld%lld", &l, &r);
        long long ans = 0;
        while (l > 0 || r > 0) {
            ans += r - l;
            l /= 10;
            r /= 10;
        }
        printf("%lld\n", ans);
    }
}

That's the entire solution. Seven lines in the loop.

The loop is the summation in disguise: each iteration is the next power of 10. On entry to iteration $k$, we have $l$ replaced by $\lfloor l/{10}^k\rfloor$ and $r$ replaced by $\lfloor r/{10}^k\rfloor$, so ans += r - l adds the position-$k$ term $\lfloor r/{10}^k\rfloor -\lfloor l/{10}^k\rfloor$. The integer division at the end of the loop body advances both to the next power. The loop ends when both have been divided down to zero -- which is also when no higher digit position can change.

The Emotional Arc

This problem taught me humility. I was so conditioned to reach for digit DP on anything with "digits" in the statement that I almost missed a pure math solution. The formula fell out once I asked the right question: "How many times does each individual digit position change?"

Decompose by position, not by number. That reframing made the problem trivial.

Transfer Lesson

• "Count total X across a range" -- before reaching for DP, ask if each position/bit/digit can be counted independently. Linearity of counting.
• Floor division counts multiples -- $\lfloor r/d\rfloor -\lfloor l/d\rfloor$ counts how many multiples of $d$ lie in $(l,r]$. Fundamental identity.
• If you're building a complex DP and the constraints are very generous (${10}^9$) -- you're probably overthinking. Look for a closed-form or per-digit decomposition.

---

See also: Contribution Technique | Binary Search | Pattern Recognition Guide | Practice Ladder 1700-2100