Digit DP counts or optimizes over numbers with digit-level constraints by constructing them digit by digit, from the most significant to the least significant, while tracking a small piece of state. The runtime is proportional to the number of digits times the state size, replacing brute-force iteration over the range.

Digit DP counts how many numbers in a range [0, N] (or [L, R]) satisfy a given digit-level property. The algorithm builds numbers one digit at a time, left to right, and uses memoization to avoid redundant work.

At each position, the allowed range for the next digit depends on whether the prefix placed so far still matches N exactly. If it does, the next digit is bounded by the corresponding digit of N. As soon as a digit is placed strictly below that limit, every subsequent digit can be anything from 0 to 9. This constraint is captured by the tight flag, which we will visualize with a concrete example shortly.

The signal is a count of numbers in a range [L, R] whose validity depends on individual digits, with a bound (often 10^9 or larger) too big to iterate through. Digit DP handles up to 18 or 19 digits efficiently. Typical shapes:

Every digit DP solution is built around a recursive function that processes one digit position at a time, from the most significant digit to the least significant. The state typically includes:

The Tight Constraint Rule

If tight is true and the placed digit equals the corresponding digit of N, tight stays true. If the placed digit is smaller, tight becomes false and stays false for all remaining positions. The decision tree later in this section makes this concrete.

The Leading Zeros Issue

Counting up to N usually includes 0. But leading zeros distort some properties. Is 007 a 3-digit number with unique digits? Leading zeros should not count toward placed-digit invariants.

The fix is a started flag (or equivalently, a marker for whether any non-zero digit has been placed). When started is false, placing a 0 keeps the path in the leading-zeros phase and 0 is not added to the used-digit set.

Range Queries via Subtraction

Most problems ask for the count in [L, R], not [0, N]. The standard approach:

count(L, R) = count(0, R) - count(0, L - 1)

A single function counts valid numbers from 0 to an upper bound; calling it twice yields the range count. This is the same prefix-sum decomposition, applied to digit DP.

The Decision Tree

The recursion for a 2-digit number with N = 25:

Placing 0 or 1 at position 0 forces the final number below 25, so tight becomes false and position 1 has the full range 0-9. Placing 2 keeps tight as true, restricting position 1 to 0-5.

Problem Statement

Given an integer n, return the count of all numbers x where 0 <= x < 10^n such that all digits in x are unique.

Examples:

Intuition

The brute-force approach checks every number from 0 to 10^n - 1 and verifies that no digit repeats. For n = 8, that is 100 million numbers. It works but is slow.

Digit DP tracks which digits have already been used via a 10-bit bitmask (one bit per digit 0-9) and skips any digit already in the mask. The bitmask is the problem-specific state added on top of pos, tight, and started.

Step-by-Step Trace

For LC 357 with n = 2, the upper bound is 99 and digits = [9, 9]. Because every digit of the bound is 9, the tight branch only fires along the path 9 -> 9, and tight never has to constrain a non-9 limit. To exercise the tight flag, the trace below uses a different bound: count unique-digit numbers in [0, 234]. Same algorithm, same code, with digits = [2, 3, 4].

Let f(pos, tight, mask, started) denote the recursive call. The root call is f(0, 1, 0, 0) with digits[0] = 2, so limit = 2.

This trace shows the two situations the tight flag handles:

The started flag plays a separate role. At d=0, pos=0, no real digit has been placed yet, so the recursion descends with started=0 and the leading zero is not added to the digit-uniqueness mask. That same subtree counts both single-digit numbers (1-9, where started becomes true mid-recursion) and the number 0 itself (when started remains false through to the end).

For LC 357 with n = 2, the same algorithm runs but every limit is 9, so the tight branch never restricts choice meaningfully. The recursion reduces to: 10 numbers from the leading-zero subtree (0 through 9) plus 9 first-digit choices times 9 second-digit choices = 91.

Implementation

The digit DP function takes four parameters: the current position, whether the prefix is still tight against the upper bound, a bitmask of used digits, and whether a non-zero digit has been placed (started). Memoization keys on all four.

Complexity Analysis

Count Numbers with Unique Digits used a bitmask of seen digits as its state. Another common digit DP state is the running remainder modulo K, which appears whenever the property of interest is divisibility. The mechanics are identical; only the state changes.

Problem Statement

Count integers in [0, N] whose digit sum is divisible by K. (A close cousin: count integers in [0, N] that are themselves divisible by K. The state for that variant tracks the current number modulo K, not the digit-sum modulo K. The shape of the DP is the same.)

The State

Track the remainder of the running digit sum modulo K. The full state for the recursion:

At a terminal state (pos == len), return 1 if remainder == 0, else 0.

Recurrence

At each position, try every allowed digit d (constrained by tight):

solve(pos, tight, rem) = sum over d in [0, limit] of solve(pos + 1, newTight, (rem + d) mod K)

where newTight = tight && (d == limit) as before.

Implementation Sketch

The recurrence body never references the value of N directly; it only consults digits[pos] when tight is true. The complexity is O(n 2 K * 10): polynomial in the number of digits and in K, independent of the numeric value of N.

Variant: Numbers Themselves Divisible By K

To count integers x in [0, N] with x mod K == 0, change the remainder update to track the value modulo K, not the digit sum. The new state transition:

newRem = (rem * 10 + d) mod K

That is, building the number digit by digit, the running value is (prefix * 10 + d) mod K. Everything else (tight, terminal check) is identical.

This is the standard reduction that lets digit DP handle "value mod K" properties even when the value itself is too large to store directly. Only the remainder is kept in state, not the value.

What Properties Admit Digit DP

A property is "digit-DP-shaped" when it can be expressed as a running invariant that updates digit-by-digit and depends only on a small piece of state:

Properties that depend on the full value in non-decomposable ways (e.g., "is the number prime") do not admit digit DP unless reformulated. Primality has no small running invariant; verification would only be possible at the end, defeating the purpose.

The DP above counts numbers in [0, N]. Most interview questions ask for [L, R], which is the standard inclusion-exclusion split:

count(L, R) = count(0, R) - count(0, L - 1)

For example, "how many integers in [100, 234] have a digit sum divisible by 3?"

Working it out (digit-sum-divisible-by-3, including 0 in the count of [0, 0]):

The closed-form check works here because of the special structure of mod 3. For most properties (digit uniqueness, "contains the digit 7", "no two adjacent equal digits"), there is no closed form, and the digit DP is the only tractable approach.

Edge Cases For The Subtraction

The subtraction reduces every range query to two single-bound queries, which is what the digit DP solves. There is no separate algorithm for [L, R] queries; the inclusion-exclusion handles it.