ADDP-5 Digit DP · DSA · kartikvyas.in

How many numbers below 10¹⁸ (a 1 followed by 18 zeros) have digits that add up to 100? Checking each number would take millions of years. But a number is built from its digits one place at a time, and most of the places, once the number is known to be below the limit, can be anything. Digit DP counts all of them at once.

Counting up to N

The questions have the form: how many whole numbers x with a ≤ x ≤ b have some property of their digits? First turn the range into two counts from zero. Let f(N) be the count among 0, 1, …, N. Then the answer is f(b) − f(a − 1): the numbers up to b, minus those below a. Watch the − 1: f(b) − f(a) would lose a itself.

Now write N with its digits, say L of them, and think of every number from 0 to N as written with exactly L digits, with zeros in front when it is shorter (7 becomes 0007 when N = 2357). A number is then a choice of one digit per place, from the left.

Tight or free

The limit “at most N” affects a place only while all the digits chosen so far equal N’s digits. Call that state tight. While tight, the next digit can be at most N’s digit at that place:

a smaller digit makes the number smaller than N whatever comes after: the rest of the places are now free, 0 to 9 each;
N’s own digit keeps the number tight;
a larger digit would make the number larger than N: not allowed.

Once free, always free. So every number up to N leaves the tight path at exactly one place (or never, for N itself), by choosing a smaller digit there. That splits the count into a few blocks of free numbers, and a free block is easy to count: for a digit sum, it is the number of ways r free digits can add up to t, a small table. The figure counts the numbers up to 2357 whose digits add up to 10.

FIG ADDP-5.1Counting numbers up to N, place by place

digit, under N = 2357

ways[r][t] = strings of r digits that add up to t (a small table worked out first)

1/6

How many numbers from 0 to 2357 have digits that add up to 10? Build the number one place at a time, from the left. Each column is a place of N, headed by N's digit there; each row is a digit you could put in that place.

Step 1 of 6

The state and the code

In general, the state is (place, what the property needs to remember about the digits so far, tight or not). The rule tries every allowed digit at this place and moves to the next place. For the digit sum, “what to remember” is the sum so far:

digit_sum.pyPython

from functools import cache

def count_digit_sum(N, S):
    """How many of 0, 1, ..., N have digits that add up to S."""
    digits = list(map(int, str(N)))

    @cache
    def go(pos, total, tight):
        if total > S:
            return 0                     # too big already
        if pos == len(digits):
            return 1 if total == S else 0
        top = digits[pos] if tight else 9
        return sum(go(pos + 1, total + d, tight and d == top)
                   for d in range(top + 1))
    return go(0, 0, True)

Why the memo works. When tight is False, the count depends only on how many places are left and the sum so far, not on which digits came before. Many different beginnings reach the same (pos, total, False), and the memo answers each of them once. When tight is True, the digits so far are N’s own, so there is just one such state per place.

Cost. States: for N up to 10¹⁸, at most 19 places × 172 sums × 2 tight values, each trying 10 digits: about 65,000 steps instead of 10¹⁸. The recursion is only as deep as the number of digits, so @cache is safe in the browser.

Leading zeros

Writing 7 as 0007 adds zeros that are not really digits of 7. For a digit sum they do no harm. For other properties they do: “no two neighbouring digits are equal” would wrongly reject 7 because of “00”, and “contains the digit 0” would wrongly accept it. So add a fourth part to the state, started: False while only zeros have been placed. While not started, a 0 is not a digit of the number, so it is not compared with anything and not counted; the first nonzero digit starts the number. The number 0 itself, all zeros, needs a decision of its own: the practice problem counts it as a number with one digit, 0.

For “no two neighbouring digits equal”, the state is (place, previous digit, tight, started). A free count also has a simple formula: a started number with r more free places has 9 choices at each, anything but the previous digit, so 9ʳ ways (r nines multiplied together). The practice problem asks for this count in a range, with a and b up to 10¹⁸.