What is the tight flag for?

It records whether the digits chosen so far still match the prefix of the bound N. While tight, the next digit is capped at the digit N has in that position; once a smaller digit is placed the remaining positions are free to use 0-9.

Why memoise on position and tightness rather than on the number?

Because the numbers reach 10^18 and cannot be enumerated, while the state space is only about 19 positions times 2 tightness values times the property state. That is a few hundred states no matter how large N is.

How do I count over a range [L, R]?

Solve the prefix form f(X), the count of valid numbers in [0, X], and take f(R) - f(L-1). Digit DP counts upward from zero, so every range query reduces to two calls.

Digit DP

Digit DP is a technique to count integers in a range [0, N] that satisfy a specific property (e.g., no digit 4).

LIMIT

Target

Digit

Found (0)

—

Pos 0: Tight=true, Limit=2. Exploring digits 0-2...

Trying digit 0...

Max 100

Intuition

Counting numbers one by one is too slow if N is large (e.g., 10¹⁸). Instead, we "construct" the numbers digit by digit from left to right. This allows us to count huge ranges in logarithmic time O(log N).

Concept

State representation:

pos: Current digit position we are filling (from left).
tight: Boolean. If true, we are restricted by the digits of N. We can place digits from 0 to N[pos]. If false, we can place any digit 0-9.
valid: (Optional) Tracks if the property is maintained.

Memoization: We store results for dp[pos][tight][state] to avoid re-calculation.

How it Works

Algorithm:

Convert N to a string or array of digits.
Start recursion from the first digit with tight = true.
At each step pos, iterate through possible digits d from 0 to limit (where limit is N[pos] if tight is true, else 9).
Update tight for the next state: newTight = tight && (d == limit).
Sum up the results from valid recursive calls.

Step-by-Step Breakdown

Visualizing the Construction:

Root: Start at most significant digit.
Branches: Each branch is a choice of a digit (0..9).
Pruning: Branches that violate the property are cut off.
Aggregation: Leaf nodes (valid numbers) contribute 1 to the count.

When to Use

Applications:

Counting integers in large ranges (up to 10¹⁸).
Properties related to digits (sum of digits, specific digits, palindromes).

When NOT to Use

Small Range: If N is small, simple iteration is faster and simpler.
Non-Digit Properties: Properties like "divisible by X" (though sometimes possible with extra state) are harder.

How to Identify

"Count numbers between L and R satisfying...", "Digit sum equals K".

Sample Problems

Digit DP - Count Numbers without 4

The problem visualized here.

Numbers At Most N Given Digit Set

Construct numbers using specific digits.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description

Max Path Sum

Introduction

Complexity

Time (Best)

O(log N)

Time (Average)

O(log N * 10)

Time (Worst)

O(log N * 10 * StateSize)

Space

O(log N) (Recursion Depth)

Digit DP Code

1var countNumbers = function(n) {
2    const s = n.toString();
3    const memo = {};
4
5    const dp = (idx, tight, has4) => {
6        if (has4) return 0; // Invalid if it contains 4
7        if (idx === s.length) return 1; // Valid number formed
8
9        const key = `${idx}-${tight}-${has4}`;
10        if (memo[key] !== undefined) return memo[key];
11
12        let ans = 0;
13        const limit = tight ? parseInt(s[idx]) : 9;
14
15        for (let d = 0; d <= limit; d++) {
16            const newTight = tight && (d === limit);
17            const newHas4 = has4 || (d === 4);
18            ans += dp(idx + 1, newTight, newHas4);
19        }
20
21        return memo[key] = ans;
22    };
23
24    return dp(0, true, false) - 1; // Subtract 0 if not counted or range starts at 1
25};

Related Lessons