Digit DP: Counting Numbers With a Property in a Range

"How many numbers between 1 and 10^18 have no two equal adjacent digits?" You can't loop over 10^18 values, but you can walk the digits. That's digit DP.

Turn a range into prefixes

Write a function count(N) = how many numbers in [0, N] satisfy the property. Then the answer for [L, R] is count(R) - count(L - 1).

State

• pos: which digit of N we're filling.
• tight: whether every digit so far equals N's prefix (if so, the next digit can't exceed N's digit at pos).
• started: whether we've placed a non-zero digit yet (handles leading zeros).
• problem state: whatever the property needs, such as the previous digit, the digit sum mod k, or a bitmask of used digits.

Example: no two equal adjacent digits

from functools import lru_cache

def count(N):
    if N < 0: return 0
    digits = list(map(int, str(N)))
    @lru_cache(None)
    def go(pos, prev, tight, started):
        if pos == len(digits):
            return 1
        limit = digits[pos] if tight else 9
        total = 0
        for d in range(limit + 1):
            if started and d == prev:
                continue
            total += go(pos + 1,
                        d if (started or d) else -1,
                        tight and d == limit,
                        started or d != 0)
        return total
    return go(0, -1, True, False)

def in_range(L, R):
    return count(R) - count(L - 1)

Complexity

States are positions (about 19) × problem state × 2 × 2, each trying 10 digits. That's tiny compared to the range, typically well under a million operations.

Common properties

• Digit sum divisible by k (state: sum mod k).
• Numbers with at most k non-zero digits (state: count used).
• Numbers whose digits are all distinct (state: 10-bit mask).
• Count occurrences of digit d across all numbers up to N.

Pitfalls

Leading zeros silently break "adjacent digit" or "distinct digit" properties; that's what started is for. And memoising on tight=True states is fine within one N, but clear the cache between different N values.

Disclosure: written by the linkjob.ai team (real-time coding interview help). Free to reuse for practice.