Digit DP
A technique to count integers in a range [0, N] that satisfy a specific property (e.g., no digit 4).
Target N
Valid Numbers Found ()
Ready
1x
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
Counting numbers one by one is too slow if N is large (e.g., 10^{18}). 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^{18}).
- 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".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.