Digit DP in Python: counting numbers with a property

Why this lesson matters

Many problems ask you to count numbers in a range, where each number must follow a rule about its digits. For example, count the numbers from 1 to 1000 whose digits never repeat next to each other. Or count the numbers up to 10^18 whose digits add up to 20. A loop that checks every number works for small limits. For 10^18 it does not. A fast computer that does about a billion simple steps per second would need about 31 years to check 10^18 numbers, and a plain Python loop is slower than that.

Digit DP (digit dynamic programming) solves this kind of problem without visiting every number. Dynamic programming means you solve a big problem by solving smaller parts once and remembering the answers. In digit DP, the smaller parts are the prefixes of the numbers, the first few digits. You build each number one digit at a time, from left to right, and you remember how many ways the rest of the number can be finished.

By the end of this lesson you will be able to explain what a tight flag and a started flag are, count numbers with a neighbour rule and with a digit-sum rule, count a range by subtracting two results, and write the Python code for a digit DP from first principles.

This lesson does not cover the interval tables from lesson 22, which fill a table by the length of a range. Digit DP works on the digits of one number.

Reading the code in this lesson

The code uses a few Python features. You need only these to follow it.

• str(n) turns the number 121 into the text "121". int(c) turns the character "1" back into the number 1. The list comprehension [int(c) for c in str(n)] does this for every character and gives [1, 2, 1].
• A list such as digits holds values in order. The first value has index 0, so digits[0] is 1 for 121.
• range(limit + 1) gives the numbers 0, 1, up to limit. The end value is not included, so the + 1 is needed to include limit.
• A dict such as memo stores answers under keys. memo[key] = total saves one answer, and key in memo checks whether it is saved. A key can be a tuple, which is a fixed group of values in parentheses, such as (1, -1, True).
• A function can be defined inside another function. The inner function go can read digits and memo from the outer one.
• x if condition else y is a one-line choice. 1 if started else 0 gives 1 when started is True and 0 when it is False.
• The last two lines of each program are if __name__ == "__main__": and a call to main(). Python runs main only when you start the file directly. If another file imports the file, main does not run.

Counting by hand first

Start with a small problem. Count the numbers from 1 to 121 whose neighbouring digits are never equal. Call such a number good. The number 102 is good, because 1 and 0 differ and 0 and 2 differ. The number 11 is not good, because its two 1s are next to each other. The number 110 is not good, because the first two digits are equal.

Count the good numbers in three groups.

• One-digit numbers, 1 to 9. A single digit has no neighbours, so all 9 are good.
• Two-digit numbers, 10 to 99. The first digit is one of 1 to 9. The second digit is one of 0 to 9, but it must differ from the first. That leaves 9 choices for each first digit, so 9 times 9 gives 81 good numbers.
• Three-digit numbers, 100 to 121. The first digit is 1. Split by the second digit.
  • Second digit 0. The third digit must not be 0, so it is one of 1 to 9. That gives 101 to 109, which is 9 numbers. The number 100 is not good.
  • Second digit 1. It equals the first digit, so every number from 110 to 119 fails.
  • Second digit 2. This is the top of the range, because the bound is 121. The third digit can only be 0 or 1. Both 120 and 121 are good, which is 2 numbers.

The total is 9 + 81 + 9 + 2 = 101. Keep this number in mind, because the program in the next section gives the same answer.

Notice the shape of the count. The good three-digit numbers depend on the first two digits only through the last digit placed. Once you know the second digit is 0, the number of good endings is the same no matter what came before. A digit DP uses that fact. It remembers only what the rest of the number needs.

The idea: build the number one digit at a time

Write the bound N as a list of digits. For 121, the digits are 1, 2 and 1. A digit DP walks through the positions of this list, from the leftmost to the rightmost. At each position it chooses a digit, and it asks two questions before it moves on.

• Which digits are allowed here? The rule of the problem decides this. For the neighbour rule, the digit must differ from the digit placed just before it.
• What must I remember for the rest of the number? For the neighbour rule, the only thing that matters is the last digit placed. For a digit-sum rule, the thing that matters is the sum so far.

When the walk reaches the end of the digits, the number is complete. It is counted if the rule holds.

The walk is a search through all candidate numbers, but two ideas stop it from being slow.

1. Caching. Two different prefixes that end with the same state have the same number of ways to finish. The DP stores the answer for each state the first time it is computed, and reuses it later.
2. The tight flag, explained next, keeps the walk from counting numbers above N.

The tight flag: staying under the bound

Suppose you have placed the first digit of 121 as 1. The number so far is 1 followed by nothing, and it matches the bound's first digit. The second digit may be 0 or 1 and still stay under 121. It may also be 2, which stays on the bound and forces the third digit to be at most 1. If the second digit is 0 or 1, the rest of the number is free. Each remaining position can hold any digit from 0 to 9.

The tight flag records whether the digits so far equal the first digits of N exactly. When tight is True, the next digit may go no higher than the matching digit of N. When tight is False, the next digit may be anything from 0 to 9.

A tight state is reached by only one path through the walk, the path that copies N. Because of that, the program does not cache tight states. The free states are the ones that repeat, so they are the ones cached.

The started flag: leading zeros are not digits

When you place digits for a shorter number, the walk places zeros in front of it. The number 7 has one digit, but a three-position walk writes it as 007. The zeros in front are not part of the number. For the neighbour rule, though, two zeros in a row look like two equal neighbours, and 007 would fail the rule for the wrong reason.

The started flag records whether a non-zero digit has been placed yet. Before the first non-zero digit, a zero is a leading zero. It does not count as a digit, and it does not set the last digit. The walk treats the number as beginning at the first non-zero digit.

With both flags, the state of the walk is the position, the last digit placed, the tight flag and the started flag. The program below passes these four values to go and uses pos, prev and started as the cache key.

Worked example 1: no equal neighbours, up to N

The rule is that neighbouring digits are never equal. The task is to count the good numbers from 1 to N. Here is the complete Python program. It counts the good numbers up to N and then checks the answers against a plain loop for every N from 0 to 5000.

Save it as no_adjacent_equal.py and run it with python3 no_adjacent_equal.py. The output on Python 3.14.4 is:

count(9) = 9
count(10) = 10
count(11) = 10
count(100) = 90
count(121) = 101
count(3000) = 2277
mismatches against brute force for 0..5000: 0
count(10^18) = 168856464709124010

The line for 121 gives 101, the same as the hand count. The line for 10^18 finishes quickly. The walk has 19 positions, and each position has at most 11 last-digit values and 2 started values, so the cache holds at most a few hundred entries.

The brute function is the plain loop. It is slow, so the program uses it only for N up to 5000. The check passes for every one of those values.

Walking through the first calls

Here is what happens for N = 121, whose digits are 1, 2 and 1. The first call is go(0, -1, True, False). It is at position 0, has no last digit, is tight and has not started.

• The limit is the first digit of N, which is 1. The loop tries 0 and 1.
• Digit 0 keeps the number unstarted. The tight flag turns off, because 0 is below 1. The call go(1, -1, False, False) counts all the numbers that have one or two digits. Those are the numbers from 1 to 99, which give 9 + 81 = 90 good numbers. The call returns 90.
• Digit 1 starts the number. It is still tight, because 1 equals the limit. The call go(1, 1, True, True) covers the numbers that start with 1 and stay under 121.

Inside go(1, 1, True, True) the limit is the second digit of N, which is 2. Digit 0 is allowed. It gives go(2, 0, False, True), which is free, so the last digit may be 1 to 9. That call returns 9, the numbers 101 to 109. Digit 1 is skipped, because it equals the last digit. Digit 2 is tight. It gives go(2, 2, True, True), whose limit is 1. Digit 0 gives the number 120 and digit 1 gives the number 121. Both are good, so that call returns 2.

Adding the parts gives 90 + 9 + 2 = 101. Each branch of the loop is one group from the hand count.

Why the key can hold -1

The first call has no last digit, so prev is -1. A key in the cache is a tuple, and -1 is a normal value inside a tuple. So the key (0, -1, False) works with no shift. The cache is a dict, not a fixed array, so the program never needs a slot for each possible value. A key that was never written is simply missing, and the program checks for that with key in memo.

A Java version of this lesson uses an array, and its array index cannot be -1. That is why the Java version shifts prev by one. Python does not need the shift here. The list-based mistake, where -1 silently picks the last slot, is shown in the common mistakes section.

Worked example 2: digits that add up to a target

The second rule is different. Count the numbers from 0 up to N whose digits add up to a target sum S. For example, with S = 10, the number 19 counts because 1 + 9 = 10, and 28 counts because 2 + 8 = 10.

Here the state is the position and the sum so far. A leading zero adds nothing to a sum, so the started flag is not needed. The only thing to stop early is a sum that is already too large. If the sum passes S, no later digits can bring it back down, because every digit is zero or more.

The core of the walk is this part. It is the same walk as before, with total in place of prev.

def go(pos, total, tight):
    if total > target:
        return 0
    if pos == len(digits):
        return 1 if total == target else 0
    key = (pos, total)
    if not tight and key in memo:
        return memo[key]
    limit = digits[pos] if tight else 9
    count = 0
    for d in range(limit + 1):
        count += go(pos + 1, total + d, tight and d == limit)
    if not tight:
        memo[key] = count
    return count

The early stop total > target is what keeps the walk fast. The full program is below. It contains count_sum_up_to, which holds the walk above, and count_sum_range, which is explained in the next section.

Run it with python3 digit_sum.py. The output on Python 3.14.4 is:

countUpTo(100, 10) = 9
countRange(100, 200, 10) = 10
countUpTo(999, 27) = 1
mismatches against brute force: 0
countUpTo(10^18, 1) = 19
countRange(20, 40, 5) = 2

The first answer is 9 because the numbers from 0 to 100 with digit sum 10 are 19, 28, 37, 46, 55, 64, 73, 82 and 91. The third answer is 1 because 999 is the only number up to 999 with digit sum 27. The fifth answer is 19 because the numbers with digit sum 1 are the powers of ten, 1, 10, 100 up to 10^18. There are 19 of them, one for each power from 10^0 to 10^18.

The mismatch check compares count_sum_up_to with a brute force count for every target from 0 to 40 and every bound from 0 to 1199. It found no mismatches.

Python does not need the bounds check that a fixed array needs. A dict has no fixed size, so no key can fall outside it. The early stop total > target is still useful, because it skips the remaining digits once the sum is already too large.

Worked example 3: counting a range

Often the question asks about a range from L to H, not from 0 to N. The standard trick is to count up to H, then take away the count up to L minus 1.

The count from L to H equals the count up to H minus the count up to L - 1, because the second count covers exactly the numbers that are too small. The function count_sum_range does this:

def count_sum_range(low, high, target):
    return count_sum_up_to(high, target) - count_sum_up_to(low - 1, target)

Take the range from 100 to 200 with digit sum 10. Count up to 200, then subtract the count up to 99. The program gives 10 for this range. The numbers are 109, 118, 127, 136, 145, 154, 163, 172, 181 and 190. Each has digit sum 10. The number 100 is not in the list, because its digit sum is 1.

The subtraction works only when the first count includes every number the second count does. Both counts start at 0, so they do. When low is 0, the value of low - 1 is -1. The function count_sum_up_to returns 0 for a negative bound, so the subtraction still gives the right answer.

Common mistakes

Forgetting the started flag

Without the started flag, leading zeros become real digits. The effect is visible on the neighbour rule. The function below uses the same walk but has no started flag, so 1 written as 001 fails, because two zeros sit next to each other.

def count_no_started(n):
    # Bug: leading zeros are treated as real digits, so 1 written as 001 is rejected.
    if n <= 0:
        return 0
    digits = [int(c) for c in str(n)]
    memo = {}
 
    def go(pos, prev, tight):
        if pos == len(digits):
            return 1
        key = (pos, prev, tight)
        if not tight and key in memo:
            return memo[key]
        limit = digits[pos] if tight else 9
        total = 0
        for d in range(limit + 1):
            if d == prev:
                continue
            total += go(pos + 1, d, tight and d == limit)
        if not tight:
            memo[key] = total
        return total
 
    return go(0, -1, True)
 
 
print("buggy count(9) =", count_no_started(9))
print("buggy count(100) =", count_no_started(100))

Its output is:

buggy count(9) = 10
buggy count(100) = 81

The correct values are 9 and 90. For 9, the buggy code also counts 0, so it prints 10. For 100, it loses the nine one-digit numbers from 1 to 9. Each one is padded to 001 through 009, and the padded zeros fail the rule. The fix is the started flag, which lets a zero in front of the first non-zero digit go unchecked.

Using 9 for every limit

The limit for a free position is 9. The limit for a tight position is the matching digit of N. If the code always uses 9, the walk counts every number up to 999 instead of up to N. The answer is too large, and it is wrong for almost every N below 999. The fix is to use digits[pos] if tight else 9.

Caching tight states

A tight state depends on the exact bound. If the cache key leaves out the tight flag, a value computed under the bound can be reused in a free state, where it does not belong. The answer can then come out wrong, and the error may show up only for some bounds. The fix is to cache only when not tight, as the program above does.

Using a list cache with -1

A cache built as a list cannot use -1 as an index. In Python, a negative index does not raise an error. It counts from the end of the list, so cache[-1] is the last item. The example below shows this with a list of 10 slots and then with an index that is too large.

cache = [0] * 10
cache[-1] = 42
print("cache[-1] reads slot 9 silently:", cache[-1])
try:
    cache[10]
except IndexError as e:
    print(type(e).__name__ + ":", e)

Its output is:

cache[-1] reads slot 9 silently: 42
IndexError: list index out of range

The write to cache[-1] raised no error, and the value landed in slot 9. The read of cache[10] raised IndexError, because slot 10 does not exist.

The silent case can give wrong answers. Take the neighbour rule with a list cache of 10 slots for each position, indexed directly by prev. For N = 1000, the first digit is 1, and every state with no digit placed yet has prev equal to -1. Those states write to slot 9, the same slot as the states whose last digit is 9. One answer overwrites the other. The program prints 828 for N = 1000, where the right answer is 819. It prints no error. This happens for every N from 1000 to 5000. The fix is the dict key used in the program, or a list of 11 slots indexed by prev + 1.

Expecting the counts to overflow

Python integers have no fixed size. The answer for 10^18 has 18 digits, and Python stores it exactly. Multiplying two large numbers also works without a special type.

print(10**18 * 10**18)

The output is:

1000000000000000000000000000000000000

Some libraries use fixed-size integer types, such as numpy's int64. Those types wrap around when a value is too large. Check the type of any count that comes from another library.

Practice

Exercise 1

Count the numbers from 1 to 500 whose digits are all odd. For example, 135 counts and 146 does not.

Show the answer

The answer is 80. There are 5 one-digit numbers (1, 3, 5, 7, 9). There are 25 two-digit numbers, because each digit is one of 5 odd digits. For three-digit numbers up to 500, the first digit must be 1 or 3, because 5 would need the rest to be 00 or less, and 500 has an even digit. That gives 2 times 25 = 50. The total is 5 + 25 + 50 = 80.

Exercise 2

Count the numbers from 1 to 1000 whose digits are strictly increasing. Strictly increasing means each digit is larger than the one before it. The number 1234 counts, and 1224 does not.

Show the answer

The answer is 129. Split by length. One-digit numbers give 9. For two digits, choose two different digits, and the first must not be 0, which gives 45 - 9 = 36. For three digits, choose three different digits, and the smallest one sits in front, so it must not be 0. That gives 120 - 36 = 84. The number 1000 does not count. The total is 9 + 36 + 84 = 129.

Exercise 3

Count the numbers from 1 to 999 that contain the digit 7 at least once.

Show the answer

The answer is 271. Count the complement first, the numbers with no 7. Each of the three positions can hold one of 9 digits (0 to 9 without 7), so there are 9 times 9 times 9 = 729 strings of three digits with no 7. One of them is 000, which is not in the range from 1 to 999, so there are 728 numbers with no 7. The answer is 999 - 728 = 271.

Exercise 4

Count the numbers from 20 to 40 whose digits add up to 5.

Show the answer

The answer is 2. The numbers are 23 (2 + 3 = 5) and 32 (3 + 2 = 5). Calling count_sum_range(20, 40, 5) gives 2 as well. The function subtracts the count up to 19 from the count up to 40.

Exercise 5

The cache below is a list of 10 slots for each position, and the code reads and writes it with prev as the index. Explain why the count for N = 1000 is wrong, and fix it.

memo = [[None] * 10 for _ in range(len(digits))]
# later, inside go, where memo[pos][prev] is read and written:
memo[pos][prev] = total

Show the answer

The value of prev runs from -1 to 9. When no digit has been placed, prev is -1, and memo[pos][-1] silently means slot 9 in Python. The states with leading zeros then share a slot with the states whose last digit is 9, so one overwrites the other. For N = 1000 the count comes out 828, and the right answer is 819. The fix is to use a dict with the key (pos, prev, started), as the program in worked example 1 does. A list also works if it has 11 slots and is indexed with prev + 1.

Summary

• A digit DP builds a number one digit at a time and remembers only what the rest of the number needs.
• The tight flag records whether the digits so far match the bound N exactly, and it limits the next digit to the matching digit of N.
• The started flag records whether a non-zero digit has been placed, so leading zeros do not break a neighbour rule.
• Only free states, where tight is False, are cached, because tight states occur on a single path.
• A count from L to H equals the count up to H minus the count up to L - 1.
• Python integers have no fixed size, so the counts do not wrap around.
• A list index of -1 means the last item and raises no error, so a cache that can hold -1 should use a dict with tuple keys.