What Is Digit DP? Count Numbers in a Range Without Touching Them All

You have a question: how many integers between 1 and 10^18 have a digit sum divisible by 7? A brute-force loop needs 10^18 iterations. That's roughly 31 years on modern hardware. By the time it finishes, you'll be retired and your interviewer will be dead.

Digit DP solves it in microseconds.

It's a dynamic programming technique for counting integers in a range that satisfy some property about their digits. Instead of checking every number, you build candidate numbers one digit at a time and count valid completions. The work is proportional to the number of digits, not the magnitude of the range. Ten thousand trillion numbers. Nineteen digits. You only look at the digits.

The Problem Shape That Breaks O(N)

These problems share a shape: count integers from 1 to N (or from L to R) where some digit-level property holds:

• Digit sum divisible by K
• No two adjacent digits are the same
• All digits are distinct
• The number contains at least three 7s
• No digit exceeds the one before it

What they have in common: the answer depends on the digits themselves, not on the number's position in a sequence. And N is always large enough that iteration is dead on arrival.

Once you recognize that shape, digit DP is the standard tool.

O(10^18) arriving at the interview

Build the Number, Don't Check It

Instead of inspecting 0, 1, 2, ..., N one at a time, imagine constructing a D-digit number from left to right. At each position you choose a digit. At the end, you've built one complete number and check whether it satisfies the property.

Digit DP counts all valid completions of all partial constructions simultaneously, using memoization. The key observation: two partial constructions in the same state (same position, same accumulated property value, same boundedness) will always produce the same number of valid completions. Cache the result and reuse it.

This is the same idea as any other memoized recursion. If you want a refresher on how that trades exponential time for polynomial time, the dynamic programming framework post covers it.

The Tight Flag Is One Boolean and It Does Everything

When you build a number digit by digit, the upper bound N constrains what you can place. If you've placed digits that match N's prefix exactly, the current digit can be at most N's corresponding digit. The moment you place a digit smaller than N's, all subsequent positions are free.

This is tracked with a boolean called tight.

Walk through N = 356:

• You place 3 (matching the hundreds digit). Tight is still True.
• You place 5 (matching the tens digit). Tight is still True.
• You place any digit d: if tight is True, d can be at most 6 (the ones digit of 356). If tight is already False, d can be 0 through 9.

If instead you had placed 2 at position 0, tight flips to False and never returns. Every remaining digit is unconstrained.

The tight flag is what turns "count all D-digit sequences satisfying P" into "count all integers up to N satisfying P." Without it, you'd be counting numbers in the wrong universe. The right universe has N as a ceiling. The wrong one has infinity. One boolean is the difference.

Digit Sum Mod K, Step by Step

Count integers from 1 to N with digit sum divisible by K.

State: (pos, tight, sum_mod).

• pos: which digit position we're filling, from 0 (most significant) to D-1.
• tight: whether every digit placed so far matches N's prefix.
• sum_mod: running digit sum modulo K.

Base case: when pos == D, return 1 if sum_mod == 0, else 0.

from functools import cache

def count_up_to(n: int, k: int) -> int:
    digits = list(map(int, str(n)))
    D = len(digits)

    @cache
    def dp(pos: int, tight: bool, sum_mod: int) -> int:
        if pos == D:
            return 1 if sum_mod == 0 else 0

        limit = digits[pos] if tight else 9
        result = 0
        for d in range(limit + 1):
            new_tight = tight and (d == limit)
            new_sum = (sum_mod + d) % k
            result += dp(pos + 1, new_tight, new_sum)

        return result

    return dp(0, True, 0)

def count_range(lo: int, hi: int, k: int) -> int:
    return count_up_to(hi, k) - count_up_to(lo - 1, k)

The range query uses the standard prefix-sum trick: count(R) - count(L-1). The subtraction is from L-1, not L. Off-by-one there undercounts by exactly the valid numbers at L. You will make this mistake once. Hopefully not during an interview.

Leading Zeros Will Break Your Count

Some problems need a started flag. Consider counting numbers with all distinct digits. The value 7 is a one-digit number, not 007. If you track a "used digits" bitmask, you shouldn't mark 0 as used from the leading zeros that pad shorter numbers to D digits.

Add a boolean started to the state: initially False, flipped to True the moment you place a nonzero digit. While started is False, placing a 0 means "haven't started yet," not "used digit 0."

For digit sum problems, leading zeros add zero and change nothing, so you can skip the flag. But for problems involving digit frequency or adjacency, it's often required.

The Math Is Lighter Than You Think

Let D be the number of digits in N (at most 19 for N up to 10^18). Let S be the size of the problem-specific state per position.

States: D × 2 × S. Transitions: at most 10 per state (one per digit choice). Total work: O(D × S × 10), completely independent of N.

For digit sum mod K: O(19 × 2 × K × 10). With K = 1000, that's 380,000 operations for a range up to 10^18. Brute force would need 10^18. Same problem. Factor of roughly 2.6 billion. No big deal.

Space is O(D × 2 × S) for the memoization table. For digit-sum mod K this is negligible. For a 10-digit bitmask (2^10 = 1024 states), it's 19 × 2 × 1024, about 40,000 entries. Still trivial.

For more on how memoization converts exponential recursion into linear state-space work, memoization time complexity has the full derivation.

These Four Signals Point to Digit DP

If all four are present, you almost certainly want digit DP. The signals:

1. Count integers in a range (phrased as "how many numbers from L to R" or "how many integers up to N").
2. The property is about the digits themselves: sum, frequency, adjacency, ordering.
3. The range is astronomically large. N > 10^6 is suspicious. N > 10^9 is nearly certain.
4. The state you need to track through a partial number is small and bounded.

The state has to fit in memory. Common patterns:

State	Size
Digit sum mod K	K
Bitmask of digits used (10 digits)	2^10 = 1024
Last digit placed	10
Digit count parity	2
Running product mod M	M

If the state space blows up (like tracking exact digit positions in all 10^18 possible values), digit DP isn't the right tool. But for most interview-level constraints, the state stays small.

The pattern recognition guide for dynamic programming covers the broader signals for when DP applies at all.

Four Bugs That Will Haunt You

Off-by-one in the range. count(R) - count(L-1), not count(R) - count(L). Easy to write wrong, easy to miss in testing because L itself is often a valid number. You've been warned.

Stale cache across calls. If you define the inner function with @cache and call count_up_to multiple times for different N values, the digits array in the closure changes but the cache doesn't. Clear it with dp.cache_clear() between calls, or restructure to avoid the closure over digits. This one is particularly fun because it silently returns wrong answers with zero errors.

"It's definitely a caching issue" and it's always your fault

Missing the started flag. For problems where digit identity matters (distinct digits, specific digit counts), treating leading zeros as real placements corrupts the count. When in doubt, add the flag.

Tight only ever becomes False. Once you place a digit strictly less than the bound, you're free for every remaining position. Tight never goes back to True. If you find yourself setting tight back to True in a transition, that's a bug, not a feature.

Start With LeetCode 902

Problem	Key State	What It Teaches
357. Count Numbers with Unique Digits	pos, used_mask	First digit bitmask problem
902. Numbers At Most N Given Digit Set	pos, tight	Canonical tight-flag introduction
233. Number of Digit One	pos, tight	Classic, many solutions but DP generalizes
600. Non-negative Integers without Consecutive Ones	pos, tight, last_bit	Binary digit DP
1012. Numbers With Repeated Digits	pos, tight, used_mask, started	Full-complexity digit DP
2719. Count of Integers	pos, tight, sum	Range [lo, hi] with digit sum bound

Start with 902. It's the most direct introduction to the tight flag with a real constraint. Then 1012 when you want a problem that demands all four state dimensions at once.

The Skeleton Never Changes

Every digit DP problem looks different on the surface. The state changes. The base condition changes. The structure never moves:

dp(pos, tight, <problem state>) =
    sum over d in [0, limit]:
        dp(pos + 1, tight and d == limit, <updated state>)

Once you internalize the tight flag and the "state as a snapshot of what matters" idea, every digit DP problem becomes the same exercise: define what you need to carry forward.

Identifying the right state is the real skill. Writing the skeleton around it takes five minutes.

That reasoning is hard to build by reading solutions. Digit DP problems require narrating your state design under time pressure, which is a different muscle from solving them quietly. SpaceComplexity runs voice-based mock interviews where you explain state choices out loud. That's where the muscle actually develops.

Key Takeaways

• Digit DP counts integers in [L, R] satisfying digit properties by constructing numbers position by position and memoizing on (pos, tight, problem state).
• The tight flag is the central mechanism. True means the current prefix matches N exactly and the next digit is bounded. False means all subsequent digits are unconstrained.
• Time complexity is O(D × S × 10) where D is the digit count and S is the problem-specific state size. Completely independent of N's magnitude.
• For range [L, R]: use count(R) - count(L-1).
• Pitfalls to memorize: stale cache between calls, missing started flag for leading zeros, off-by-one in the range subtraction.

Further Reading

• Digit DP Introduction, GeeksforGeeks
• Digit DP, USACO Guide
• CP-Algorithms: Digit DP
• LeetCode 902: Numbers At Most N Given Digit Set
• LeetCode 1012: Numbers With Repeated Digits