Digit DP

This is an extension topic beyond most interviews; it pays off in hard OAs that ask you to count the integers in a huge range (up to 10^18) whose digits satisfy some rule.

Intuition

Counting from 0 to 10^18 one number at a time is hopeless, but the work is extremely repetitive: counting 7000-7999, 8000-8999 and 9000-9999 all walk the last three digits through 000-999 in the same way. Digit DP builds numbers digit by digit from the most significant position and caches "how many ways can the remaining positions be filled, given what we know so far".

The standard state:

• pos: which digit we are filling.
• tight: whether every digit so far equals the corresponding digit of the upper bound n. If tight, the current digit can go only up to n's digit; otherwise it can be anything from 0 to 9.
• started: whether a non-zero digit has been placed yet. Leading zeros usually must not count as real digits (they are not "used" digits and do not make neighbors).
• the problem-specific summary of the prefix: previous digit, digit sum modulo k, mask of used digits, number of ones so far...

Ranges are handled with prefix counts: count(lo..hi) = count(0..hi) - count(0..lo-1).

When to use it in interviews / OAs

• "How many integers in [L, R] ..." with R up to 10^9 or 10^18 and a condition on the digits (distinct digits, no forbidden pattern, digit sum, alternating parity, adjacent digit differences).
• "Total number of times digit d appears in all numbers up to n".
• Counting numbers at most n that can be written with a given set of digits, or in a different base (for example binary strings without consecutive ones).

Template

Write a memoized DFS over positions. Python's cache includes tight and started in the key, so no special handling is needed (in C++ one usually memoizes only the non-tight, started states).

Total count of digit 1 in 0..n. The prefix summary is "how many ones so far"; leading zeros contribute nothing, so started is not needed.

from functools import cache


def count_digit_one(n: int) -> int:
    # total number of digit 1 written when listing every integer 0..n
    digits = list(map(int, str(n)))

    @cache
    def dfs(pos: int, ones: int, tight: bool) -> int:
        if pos == len(digits):
            return ones
        limit = digits[pos] if tight else 9
        return sum(dfs(pos + 1, ones + (d == 1), tight and d == limit) for d in range(limit + 1))

    return dfs(0, 0, True)

Integers in 1..n with all digits distinct. The prefix summary is a 10-bit mask of used digits. Leading zeros must not mark digit 0 as used, which is exactly what started is for.

def count_distinct_digit_numbers(n: int) -> int:
    # how many integers in [1, n] have pairwise different digits
    digits = list(map(int, str(n)))

    @cache
    def dfs(pos: int, used: int, tight: bool, started: bool) -> int:
        if pos == len(digits):
            return int(started)  # the all-zero "number" is not counted
        limit = digits[pos] if tight else 9
        total = 0
        for d in range(limit + 1):
            if not started and d == 0:  # still in the leading zeros
                total += dfs(pos + 1, used, tight and d == limit, False)
            elif not used >> d & 1:
                total += dfs(pos + 1, used | 1 << d, tight and d == limit, True)
        return total

    return dfs(0, 0, True, False)

Adjacent digits differ by at least 2. Here the summary is the previous digit, and only digits after the number has started are compared.

def count_windy(n: int) -> int:
    # integers in [1, n] whose adjacent digits differ by at least 2
    if n <= 0:
        return 0
    digits = list(map(int, str(n)))

    @cache
    def dfs(pos: int, prev: int, tight: bool, started: bool) -> int:
        if pos == len(digits):
            return int(started)
        limit = digits[pos] if tight else 9
        total = 0
        for d in range(limit + 1):
            nt = tight and d == limit
            if not started:
                total += dfs(pos + 1, d, nt, d != 0)
            elif abs(d - prev) >= 2:
                total += dfs(pos + 1, d, nt, True)
        return total

    return dfs(0, 0, True, False)


def count_in_range(lo: int, hi: int, count_upto) -> int:
    # count_upto(x) counts valid integers in [0, x]; the answer for [lo, hi] is a difference
    return count_upto(hi) - (count_upto(lo - 1) if lo > 0 else 0)

Complexity

Time is (number of positions) x (number of prefix summaries) x 2 (tight) x 2 (started) x 10 (digit choices). For 10^18 there are 19 positions: the digit-one count has about 19 * 20 * 2 summaries, the distinct-digits count about 19 * 1024 * 4. Both run instantly. Space is the number of cached states.

Common pitfalls

• Leading zeros: "0042" is the number 42. Without started, zeros at the front get treated as digits (marking 0 as used, or being compared to the next digit).
• Counting zero: decide whether 0 is a valid answer and keep it consistent between count(hi) and count(lo - 1).
• The lo - 1 boundary: when lo = 0, there is nothing to subtract; str(-1) would break the digit list.
• Tight in the memo (other languages): if you memoize without tight in the key, only store results computed with tight == False, because a tight state depends on n's remaining digits.
• Stale caches: the cached function depends on digits, so define it inside the counting function (as above) to get a fresh cache for each bound.
• Too large a summary: if the prefix summary can take millions of values (for example the exact digit sum of a 100-digit bound times a large modulus), check the state count before coding.

Interview variations

• Numbers at most n built from a given digit set: summary is nothing at all; only tight and started matter.
• Numbers with at least one repeated digit: complement of the distinct-digits count.
• Non-negative integers without consecutive ones in binary: same template over the binary digits of n, summary is the previous bit.
• Count integers whose digit sum lies in [a, b]: summary is the running digit sum.
• Stepping numbers (adjacent digits differ by exactly 1) in a range given as strings: summary is the previous digit; ranges come as big strings, so compute count(hi) - count(lo) + check(lo).
• Beautiful integers (equal numbers of even and odd digits and divisible by k): summary is (even minus odd, value mod k).