Digit DP and the Digit Sum problem
Some counting problems ask how many integers up to a bound have a property of their decimal digits: a digit sum divisible by 4, a digit sum between 10 and 20, no two equal digits next to each other. The bound can be far too large to test the integers one by one. Digit DP is dynamic programming that counts them by building the numbers one digit at a time. The first problem is Digit Sum.
You get a positive integer and an integer . Count the integers from 1 to whose digit sum, in base ten, is a multiple of . Print the count modulo .
The input holds on the first line and on the second.
Constraints
Sample 1 · Input
30 4
Output
6
Sample 2 · Input
1000000009 1
Output
2
Sample 3 · Input
98765432109876543210 58
Output
635270834
In the first sample and . Six numbers from 1 to 30 have a digit sum that is a multiple of 4: 4, 8, 13, 17, 22 and 26. In the second sample , so every number counts and the answer is itself, 1,000,000,009. The program prints the remainder of that modulo , which is 2.
The direct solution is a loop over the numbers from 1 to that adds up the digits of each one. It is correct but far too slow. Suppose were only , about the largest bound a 64-bit integer can hold. Even at numbers a second the loop would run for seconds, which is more than 300 years. In this problem can have 10,000 digits.
A bound with 10,000 digits has only 10,000 digit positions, though. So the program we write loops over the digit positions of , and at each position it counts whole groups of numbers at once, without listing them.
Tight and loose prefixes
The second fact is how the prefix compares with the bound. After the prefix 24 any digit may follow, because 240 to 249 are all at most 253. After the prefix 25 only 0, 1, 2 and 3 may follow, because 254 is already too large. The prefix 25 is restricted because it is equal to the first two digits of the bound, while 24 is already smaller than them.
A prefix that is equal to the first digits of the bound is called tight, and its next digit can be at most the bound's next digit. A prefix that is smaller than the first digits of the bound is called loose, and any digit from 0 to 9 can follow it: the number is already below the bound at an earlier position, and no later digit changes that.
The top row follows the tight prefix. It stays tight only by taking the bound's own next digit. Any smaller digit makes it loose, and a loose prefix stays loose whatever is added to it. So at every length exactly one prefix is tight, the first digits of the bound itself, and all the other prefixes are loose.
So a state is made of three things: how many digits have been placed, the remainder of their digit sum, and whether the prefix is tight. Its value is the number of prefixes that fit that description. For the prefixes of one length we write loose[r] for the number of loose prefixes whose digit sum has remainder , and tight[r] for the number of tight ones. After two digits of the example, loose[0] is 6, for the prefixes 00, 04, 08, 13, 17 and 22.
The transition from one digit to the next
Every prefix is a prefix one digit shorter with one more digit on the end. So the transition takes the counts for one length and builds the counts for the next. The transitions for the frog, the stairs and the coins looked back: each entry read the earlier entries it was built from. This one pushes forward instead. It takes each state of the shorter length, tries every digit that may be appended, and adds the state's count to the state of the longer prefix. There are two rules:
- A loose prefix with remainder can take every digit from 0 to 9. The longer prefix is loose and has remainder .
- A tight prefix with remainder can take every digit up to the bound's digit at this position. The remainder changes in the same way. The longer prefix is tight if is the bound's digit and loose if is smaller.
The base case is the empty prefix. No digit has been chosen, so its digit sum is 0. The empty prefix has not gone below the bound, so it is tight, and its first digit can be at most the bound's first digit. tight[0] therefore starts at 1 and every other count at 0. Climbing Stairs began in the same way, with one way to stand on the floor. The counts for one length are built only from the counts for the length before, so the program computes one length at a time and goes through the digits of the bound from left to right.
In the example the bound's first digit is 2. The empty prefix takes 0 and 1, which make the loose prefixes 0 and 1, and it takes 2, which makes the tight prefix 2:
The second digit of the bound is 5. Three prefixes are extended, and the table has a row for each, with the number of new prefixes it adds to each remainder:
| Prefix | Digits it takes | New loose, r = 0, 1, 2, 3 | New tight |
|---|---|---|---|
| 0, loose | 0 to 9 | 3, 3, 2, 2 | |
| 1, loose | 0 to 9 | 2, 3, 3, 2 | |
| 2, tight | 0 to 4, then 5 | 1, 1, 2, 1 | 25, with r = 3 |
| Total | 6, 7, 7, 5 | 25, with r = 3 |
The prefix 0 has digit sum 0, so its row sorts the ten digits by their own remainder: 0, 4 and 8 give remainder 0; 1, 5 and 9 give 1; 2 and 6 give 2; and 3 and 7 give 3. The tight prefix 2 becomes loose with the digits 0 to 4 and stays tight with 5, as 25, which has digit sum 7. The totals account for the 25 loose prefixes 00 to 24 and the one tight prefix.
At the third digit the grouping saves work. There are 25 loose prefixes, and the transition handles them as four counts. A prefix with remainder 0 finishes with remainder 0 if its last digit is 0, 4 or 8, so the 6 prefixes of that kind give finished rows. A prefix with remainder 1 needs a 3 or a 7, one with remainder 2 needs a 2 or a 6, and one with remainder 3 needs a 1, a 5 or a 9.
The tight prefix 25 takes 0, 1 and 2 and becomes 250, 251 and 252, and of those only 251 has a digit sum that is a multiple of 4. Together that makes
loose rows with remainder 0. With the digit 3 the tight prefix becomes 253 itself, which has digit sum 10 and remainder 2. The other three remainders are counted in the same way, and the finished counts are:
The rows with remainder 0 are the numbers from 0 to 253 whose digit sum is a multiple of 4. There are 62 loose ones and no tight one. One of the 62 is the row 000, the number 0, which the problem leaves out because it counts from 1. So the answer for is 61.
Worked example
Predict the counts yourself
The trace runs the same transition on our example, one digit of the bound at a time, with shown as the divisor. With Predict the next step switched on, you work out the new loose[0] before it appears. Two presets are edge cases: the bound 26 counts itself, because its digit sum is 8, and for the bound 0 the only row is 0, so the answer is 0.
Before reading any digits, one empty prefix is equal to the bound and has remainder 0.
- digits read
- 0
- divisor
- 4
- bound
- 253
Change the example input
Current result: 61
The Digit Sum program
The program reads as a string and goes through its digits from left to right. The arrays loose and tight hold the counts for the prefixes read so far. For each digit, the program builds the counts for prefixes one digit longer in two new arrays, and then those arrays take the place of the old ones.
MOD = 10**9 + 7
def count_up_to(k, d):
"""Integers 1 to k whose digit sum is a multiple of d; k is a string."""
loose = [0] * d
tight = [0] * d
tight[0] = 1
for limit in map(int, k):
next_loose = [0] * d
next_tight = [0] * d
for r in range(d):
for digit in range(10):
next_loose[(r + digit) % d] += loose[r]
for digit in range(limit):
next_loose[(r + digit) % d] += tight[r]
next_tight[(r + limit) % d] += tight[r]
loose = [count % MOD for count in next_loose]
tight = next_tight
return (loose[0] + tight[0] - 1) % MOD
k = input().strip()
d = int(input())
print(count_up_to(k, d))On the first sample the program prints 6.
Python details
With CPython 3.14 on a 2025 laptop this program took about 0.8 seconds for a bound of 10,000 nines with , and the judge allows 2 seconds. AtCoder also offers PyPy, which runs loops like these several times faster.
The three additions inside the loop over r are the transition. A loose prefix takes all ten digits. A tight prefix becomes loose with a digit below limit, the bound's digit, and stays tight with limit itself.
The new counts go into new arrays because every prefix has to be extended exactly once. If the additions went into loose itself, a count that had just been increased would be read again later in the same pass and extended a second time.
The counts can grow far beyond , so the program reduces them after every digit. Reducing early does not change the final remainder, by the rule about remainders of sums that we used for the digit sums.
The last line adds the two counts for remainder 0, because itself counts when its digit sum is a multiple of , and subtracts 1 for the number 0.
For each digit of the program goes through remainders and makes at most 20 additions for each. A bound of digits therefore takes time, and at the limits of the problem that is
The memory is four arrays of counts, however long the bound is.
Counting over a range
Digit Sum counts from 1 up to a bound. Many problems count over a range from to instead. Counting from 0 up to a bound is enough for those too, because a range is the difference of two such counts. Let be the number of integers from 0 to that have the property, with when is negative. The integers up to are the integers below together with the integers from to , so the count for the range is
Prefix sums answered range-sum queries with the same subtraction. The second term is and not , because itself belongs to the range.
For example, take the integers from 100 to 200 whose digit sum is a multiple of 4. Counted from 0, there are 49 of them up to 200 and 25 up to 99:
Both counts include the number 0, and the subtraction removes it.
Digit DP as a memoized recursion
Digit DP can also be written as a recursive function whose arguments are the state. Many prefixes lead to the same arguments, so the function writes the result for each set of arguments in a memo the first time it computes it, and looks it up when the same arguments come back. The next problem uses that form.
You get two numeric strings num1 and num2 and two integers min_sum and max_sum. An integer is good if and its digit sum is at least min_sum and at most max_sum. Return the number of good integers modulo .
Constraints
Sample 1 · Input
num1 = "1", num2 = "12", min_sum = 1, max_sum = 8
Output
11
Sample 2 · Input
num1 = "1", num2 = "5", min_sum = 1, max_sum = 5
Output
5
In the first sample the 11 good integers are 1 to 8, 10, 11 and 12. The 9 is missing because its digit sum is above 8.
The condition is on the digit sum itself, and a remainder would not say enough, so the state keeps the exact sum of the digits placed so far. A sum above max_sum cannot come back down, so a prefix with such a sum is dropped. The sums that remain run from 0 to at most 400, which is 401 values.
The arguments of ways(pos, s, tight) describe a prefix: pos digits have been placed, they add up to s, and tight says whether they are equal to the first digits of the bound. It returns the number of ways to choose the remaining digits so that the finished number is good. The value of a state means something different here. In Digit Sum the arrays counted how many prefixes lead into a state. This function counts how many ways there are to finish the number from a state. The answer for a bound is the value for the empty prefix, with nothing placed, sum 0 and tight true.
The transition is the same loop over the next digit. A tight prefix takes the digits up to the bound's digit and a loose one takes all ten, and each choice is a recursive call for a prefix one digit longer. There are two base cases. A prefix whose sum has passed max_sum has 0 ways. A finished number has 1 way if its sum is at least min_sum and 0 ways if not.
Take the bound 12 from the first sample. The empty prefix can take 0 or 1. After 0 the prefix is loose with sum 0. Any last digit from 1 to 8 finishes it, while 0 leaves the sum below min_sum and 9 takes it above max_sum, so the call for this prefix returns 8. After 1 the prefix is tight with sum 1, the last digit can be 0, 1 or 2, and the call returns 3. The first call returns their sum, .
Without a memo the function would follow every prefix on its own, which is no faster than the slow loop. With a memo each state is computed once. Under a longer bound, the loose prefixes 13 and 22 both lead to the call with two digits placed and sum 4, and the second of those calls returns the stored answer, just as the two prefixes shared one count in Digit Sum.
The range needs , and the two ends arrive as strings of digits, because is too large for a 64-bit integer. Rather than subtract 1 from a string, which takes extra code in C++, the program computes , which leaves num1 out of the range, and adds 1 when num1 itself is good. In the first sample and 1 is good, so the answer is .
The Count of Integers program
The function count_up_to is . It turns the bound into digits, starts with an empty memo and makes the first call. The memo cannot be kept from one bound to the next, because the answers in it depend on the digits of the bound and on its length.
MOD = 10**9 + 7
def count_up_to(bound, min_sum, max_sum):
"""Integers 0 to bound whose digit sum is from min_sum to max_sum."""
digits = list(map(int, bound))
@cache
def ways(pos, s, tight):
if s > max_sum:
return 0
if pos == len(digits):
return 1 if s >= min_sum else 0
limit = digits[pos] if tight else 9
total = 0
for d in range(limit + 1):
total += ways(pos + 1, s + d, tight and d == limit)
return total % MOD
return ways(0, 0, True)
def count_good(num1, num2, min_sum, max_sum):
first_is_good = min_sum <= sum(map(int, num1)) <= max_sum
return (count_up_to(num2, min_sum, max_sum)
- count_up_to(num1, min_sum, max_sum) + first_is_good) % MOD
print(count_good("1", "12", 1, 8))
print(count_good("1", "5", 1, 5))On the two samples the program prints 11 and 5.
Python details
@cache stores the result for each combination of the three arguments. ways is defined inside count_up_to, so every bound gets a new function and a new memo.
A bound of at most has at most 23 digits. With 401 sums, two values of tight and at most ten digits to try in each state, one call of count_up_to makes at most
The recursion is as deep as the bound is long. That is why Digit Sum was written as a loop: at its limits the recursion would nest 10,000 calls, and Python allows about 1,000 by default.
Leading zeros and the started flag
The zeros we put in front of the shorter numbers have done no harm so far. They add nothing to a digit sum, so 007 has the digit sum of 7. The next property looks at neighbouring digits, and there the padding gets in the way.
You get two integers and . Count the integers from to in which no two adjacent digits are equal.
The only input line holds and .
Constraints
Sample · Input
123 321
Output
171
The sample counts numbers such as 123, 130 and 321, and it leaves out numbers such as 133 and 300.
Whether a digit may be appended depends only on the digit before it. So the state keeps the previous digit, prev, where Count of Integers kept the sum.
Now pad the number 5 to the length of the bound 100. It becomes 005, and its two padding zeros look like a pair of equal neighbours. A function that compares every digit with the one before it rejects 5 for that reason, and it rejects every other number below 10 in the same way. Up to 100 there are 91 numbers without equal neighbours: 0 to 9, and the 81 two-digit numbers other than 11, 22 and so on up to 99. That function counts only the 81.
The fix is one more flag in the state. The flag started is false while every digit placed so far is a padding zero, and it becomes true at the first nonzero digit. While it is false there is no previous digit to compare with, so every digit is allowed, another zero included. Once it is true, a digit equal to prev is skipped.
The row of all zeros is the number 0. Its flag stays false to the end, and the function counts it as one number. That is right for this problem, where the range may begin at 0.
The Counting Numbers program
This is the recursion from Count of Integers with prev in the place of the sum and started as a fourth argument. Both ends of the range fit in a 64-bit integer, so the program can subtract 1 from directly, and count_up_to returns 0 for a negative bound.
def count_up_to(n):
"""Integers 0 to n in which no two adjacent digits are equal."""
if n < 0:
return 0
digits = list(map(int, str(n)))
@cache
def ways(pos, prev, tight, started):
if pos == len(digits):
return 1
limit = digits[pos] if tight else 9
total = 0
for d in range(limit + 1):
if started and d == prev:
continue
total += ways(pos + 1, d, tight and d == limit, started or d != 0)
return total
return ways(0, 0, True, False)
a, b = map(int, input().split())
print(count_up_to(b) - count_up_to(a - 1))On the sample the program prints 171.
On the sample, is 273 and is 102, and the program prints .
The first call passes 0 for prev. The value is not compared with anything: prev is only used once started is true, and by then it holds the last digit placed.
A bound of at most has at most 19 digits, so there are at most states, each with a loop over at most ten digits.
A started flag is needed whenever a zero in front of a number would change the property. That is the case for properties of neighbouring digits, of the first digit, of the number of digits, and of the product of the digits. Digit sums are unchanged by zeros in front, which is why the first two problems did without the flag.
Try the next problem before reading the answer below it. Its bound is called , and is the number of nonzero digits it asks for.
You get and . Count the integers from 1 to that have exactly nonzero digits in base ten.
The input holds on the first line and on the second.
Constraints
Sample 1 · Input
100 1
Output
19
Sample 2 · Input
25 2
Output
14
Sample 3 · Input
314159 2
Output
937
Recall In the problem above, what does a prefix have to remember, and does the state need a started flag?
In the first sample the 19 numbers are 1 to 9, the multiples of 10 from 10 to 90, and 100.
Appending a 0 leaves the number of nonzero digits as it is, and any other digit raises it by one. So the state keeps that number, together with the number of digits placed and whether the prefix is tight. A prefix with more than nonzero digits is dropped, as a sum above max_sum was, and a finished number counts when it has exactly .
The state needs no started flag. A zero in front is not a nonzero digit, so the padding changes nothing. The number 0 has no nonzero digits and is at least 1, so 0 is left out without a correction.
Time and space of these programs
- Digit Sum, as a loop
time, space - For each of the digits of the bound there are states, a loose and a tight one for each remainder, with at most ten additions each. Only the counts for two lengths are kept.
- Count of Integers
time and space - With possible sums there are states, each with a loop over at most ten digits. The memo keeps every state.
- Counting Numbers
time and space - At most states, each with a loop over at most ten digits.
In each row the time is the number of states times the choices for the next digit, at most ten. The size of the bound enters only through its number of digits , which is why a bound of 19 digits or of 10,000 is within reach.
Common mistakes
Adding the new counts into
looseitself in place of a new array.- Where it breaks
- With the bound
25and the answer should be25. After the first digitloose[0]is 2. In the second pass each of the ten additionsloose[0] += loose[0]doubles it, up to , and the tight prefix adds 5 more, so the program prints2053. - The fix
- Build the counts for the next length in new arrays that start at zero, and replace the old arrays after the pass.
Computing a range as .
- Where it breaks
- For the integers from 103 to 200 whose digit sum is a multiple of 4, gives
23. The answer is24, because 103 has digit sum 4 and belongs to the range. - The fix
- Subtract , with of a negative number equal to 0 so that works. When is a string, subtract and add 1 if itself has the property, as Count of Integers does.
Keeping the memo of one bound for the next.
- Where it breaks
- Take Counting Numbers with a memo that outlives one call of
count_up_to: a global array that is filled with -1 only once, or a cached function defined outsidecount_up_to. On the input123 321, the bound computed first stores its count under the state of the empty prefix, the call for the other bound returns that same count, and the program prints0where the answer is171. - The fix
- Start an empty memo for every bound.
Further reading
- USACO Guide, GoldDigit DP(opens in a new tab)
Solves the Odometer problem with the recursion
dp[pos][k][under][started], whereunderis the opposite of the tight flag, and lists graded practice that includes Counting Numbers. - OI Wiki, in Chinese数位 DP (Digit DP)(opens in a new tab)
Five worked problems. One of them is windy numbers, whose adjacent digits must differ by at least 2, a close relative of Counting Numbers.
- AtCoderEducational DP Contest(opens in a new tab)
Digit Sum is problem S of 26. The other problems give practice for the earlier DP lessons.
- Jeff Erickson (PDF)Algorithms, Chapter 3: Dynamic programming(opens in a new tab)
Section 3.1 speeds up a slow recursion by writing down the results of its calls, then replaces it with a loop that fills the table in the same order, and Section 3.4 sets out a step-by-step way to design a DP. Parts of this page adapt this chapter’s text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code.
