1. What is Digit DP?
Digit DP is a technique used to compute information such as counts or sums of numbers within a range [l, r], when the constraint depends on the digits of the number. Here, the bounds can be very large (up to $$$10^{18}$$$ or larger).
Instead of solving the range directly, we reduce the problem to:
$$$
where F(n) computes the required information for all numbers in the range [0, n). Thus, the main task becomes implementing a function F(n).
Although Digit DP is often presented recursively, an iterative formulation is usually easier to debug and understand once the idea is clear. This article describes the iterative viewpoint.
2. Core Idea to implement the function F(n)
To make this work cleanly, we represent all integers using the same number of digits by allowing leading zeros. Additionally, we prepend one extra leading zero to every integer so that the most significant digit is always 0. The extra leading 0 is added to all integers just to simplify base case handling.
Assume n has D digits (in the base we are working with).
All numbers are represented using exactly D digits by allowing leading zeros.
Example (D = 5):
00000
00001
00002
.
.
.
09999
In this way, we can represent all numbers as strings of equal length. If string a is lexicographically larger than string b, then a is also larger than b as an integer.
And if we have info about all strings lexicographically smaller than the string made from the integer n, then we will have info about all integers smaller than n.
To keep consistency with the string-based view:
- The 0th digit refers to the leftmost digit (MSD), which is always
0 - The 1st digit is immediately to its right
- The last digit is the LSD
The main idea is to build all valid integers from the most significant digit (MSD) to the least significant digit (LSD), while keeping partial information about only those integers that will always remain smaller than n, no matter which digit we append next. At each position, we also separately track the single prefix that is still exactly equal to the prefix of n processed so far.
3. DP state definition
Let $$$dp(i, j)$$$
represent the information (count, sum, etc.) about all prefixes of length i that:
- are already strictly smaller than the first
idigits ofn, and - satisfy some maintained property
j.
The meaning of j depends on the problem.
For example, j will represent the number of set bits used so far.
The prefix that is still exactly equal to the first i digits of n is maintained separately and extended step by step.
Base Case
The base case would be separately providing information about the prefixes less than MSD or 1-length prefix of n . As we deliberately put MSD as 0 we dont need to do anything here unless the problem specify something for empty prefixes.
4. Transition from smaller prefixes to larger prefixes
From a state dp(i - 1, j), we can append any digit from 0 to 9. Since the prefix is already smaller than n, appending any digit will keep the new prefix of length i strictly smaller than the prefix of length i of n.
We do this for each digit d in range [0, 9]
if adding d to the property j allows us to transition to k we add the contribution of $$$dp(i - 1, j)$$$ to $$$dp(i, k)$$$
5. Transition from the equal prefix
At position i-1, there is exactly one prefix that is still equal to the first i-1 digits of n and we have maintained its property till now.
Let the i-th digit of n be x.
- For every digit
dsuch that0 ≤ d < x, appendingdmakes the new prefix strictly smaller thann, If appendingdto the maintained property allows us to transition to the propertykwe update $$$dp(i, k)$$$ accordingly. - Appending digit
xkeeps the prefix equal, so we simply update the maintained properties of the equal prefix and continue to the next digit.
After processing position i, the DP table contains complete information about all prefixes of length i that are already smaller than the prefix of n.
6. Final step
We repeat this process from i = 1 up to i = D.
At the end, the DP table contains information about all integers strictly smaller than n.
To also include n itself in the computation, a simple and effective fix is to run the function for:
n + 1
This way, the final result naturally includes n.
7. Using the function for a range
Once F(n) is implemented, the answer for any range [l, r] is computed as:
$$$
8. Example problem
Given integers l, r, and k, compute the sum of all integers x in the range [l, r] such that the number of 1s in the binary representation of x is exactly k.
As discussed earlier, it is sufficient to construct a function that computes the answer for the range [0, n) using the iterative Digit DP framework.
A detailed worked example illustrating the transitions will be added later.
