Digit DP: counting numbers with a property

Why this matters

Suppose you need to count how many numbers up to one million have a rule about their digits. For example, no digit appears twice in a row. You could test each number one by one. That works for one million, but it is slow for N near 10^18, a 19-digit number, which fits in a 64-bit integer.

Digit DP is a way to count such numbers by looking at the digits of N one position at a time. DP stands for dynamic programming, the method of solving a big problem by solving smaller parts once and saving the answers. Digit DP takes a few steps for each digit, so the work grows with the number of digits in N, not with N itself.

Some terms used in this lesson:

• A digit is one of the symbols 0 to 9. The number 250 has three digits: 2, 5 and 0.
• A property is the rule a number must follow. In this lesson the rule is: no two neighbouring digits are equal. The number 121 follows it. The number 112 does not, because the two 1s are neighbours.
• A state is the information you must remember at one point in the work. Here a state holds the position in N, the digit placed just before, and a few flags.
• A flag is a yes or no value that records a fact, such as "so far the number has matched N exactly".
• Memoization means saving an answer the first time you compute it, so the same state is not computed again. The memoization lesson, the first in this module, introduced it.

The example throughout is: count the numbers from 1 to N that have no two neighbouring digits equal.

The idea with a small example

Count the numbers from 1 to 12 that have no two neighbouring digits equal.

• The numbers 1 to 9 each have one digit, so no neighbours. That is 9 numbers.
• 10 has digits 1 and 0, which are different. It counts.
• 11 has two equal neighbours. It does not count.
• 12 has digits 1 and 2, which are different. It counts.

The total is 9 + 1 + 1 = 11. A plain check of each number gives the same answer, and for 12 that is easy. For N with 19 digits, the plain check would test up to 10^18 numbers, so digit DP is needed.

Step 1: walk the digits of N and track whether you are still tight

Write N as a row of digits. For N = 250 the digits are 2, 5 and 0. Any number with three digits that is at most 250 has a first digit of 0, 1 or 2 (a first digit of 0 means the number is shorter, which is handled separately).

Build the number one digit at a time, from left to right. Keep a flag called tight, which means: so far the digits you have placed are exactly the same as the first digits of N.

• While tight is true, the next digit can go up to the matching digit of N and no further. For N = 250, if the first digit is 2, the second digit can be at most 5.
• If you place a digit smaller than N's digit, the number is already below N. tight becomes false. The remaining digits can then be anything from 0 to 9.
• If you place N's digit exactly, tight stays true.

For N = 250, the first digit can be 0 or 1, and then the rest is free, because 1xx and 0xx are already below 250. The first digit can be 2, which keeps the number tight. From there the second digit can be 0 to 5, and so on.

Two things follow. First, tight is true for only one path through the digits, the path that matches N. Second, every other path is free, so it has the same choices at every position.

Step 2: track the previous digit and the started flag

The property needs to know the previous digit, so the state also holds prev, the digit placed just before the current position.

There is one catch. Numbers shorter than N are written with leading zeros when you walk the digits of N. The number 7 is written as 007 when N has three digits. Those zeros are not real digits. Without care, the two leading zeros would be treated as neighbours that are equal, and the number 7 would be wrongly rejected.

The fix is a flag called started. It is false while only zeros have been placed. It becomes true at the first nonzero digit. While started is false, the stored prev is set to 10, which means "there is no previous digit". The digit 10 can never equal a real digit, so the first real digit is never blocked by a leading zero.

Step 3: write the recursive walk

The state has four parts: the position pos, the previous digit prev, the flag tight and the flag started. The function go returns how many valid numbers can still be completed from that state.

The base case is at the end of N's digits. A number is counted only if it has started, which means it is not the number 0. The problem asks for the numbers from 1 to N.

Inside the loop, every digit d from 0 up to limit is tried. The limit is N's digit when tight is true, and 9 otherwise. A digit equal to prev is skipped, since two neighbours cannot be equal. The new tight flag is true only if d is N's digit and we were tight already.

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
 
// Count numbers in [1, N] whose neighbouring digits are all different.
class DigitCounter {
public:
    explicit DigitCounter(std::uint64_t n)
        : digits_(std::to_string(n)),
          memo_(digits_.size() * 11 * 2, -1) {}
 
    std::int64_t count() { return go(0, 10, true, false); }
 
private:
    // prev is the digit placed just before pos. 10 means "no digit yet".
    std::int64_t go(std::size_t pos, int prev, bool tight, bool started) {
        if (pos == digits_.size()) {
            return started ? 1 : 0;  // the number 0 is not counted
        }
        std::size_t key = pos * 22 + static_cast<std::size_t>(prev) * 2 + (started ? 1 : 0);
        if (!tight && memo_[key] != -1) {
            return memo_[key];
        }
        int limit = tight ? digits_[pos] - '0' : 9;
        std::int64_t total = 0;
        for (int d = 0; d <= limit; ++d) {
            if (d == prev) {
                continue;  // two neighbouring digits are equal
            }
            bool next_started = started || d != 0;
            int next_prev = next_started ? d : 10;
            total += go(pos + 1, next_prev, tight && d == limit, next_started);
        }
        if (!tight) {
            memo_[key] = total;
        }
        return total;
    }
 
    std::string digits_;
    std::vector<std::int64_t> memo_;
};
 
int main() {
    DigitCounter twelve(12);
    std::cout << "count up to 12: " << twelve.count() << '\n';
 
    DigitCounter ninety_nine(99);
    DigitCounter nine(9);
    std::cout << "count up to 99: " << ninety_nine.count() << '\n';
    std::cout << "count from 10 to 99: " << ninety_nine.count() - nine.count() << '\n';
 
    DigitCounter n250(250);
    std::cout << "count up to 250: " << n250.count() << '\n';
}

Save the code as digit_count.cpp. Compile and run it with g++ -std=c++20 -Wall -o digit_count digit_count.cpp, then ./digit_count. The output is:

count up to 12: 11
count up to 99: 90
count from 10 to 99: 81
count up to 250: 208

The first line matches the hand count from the small example. The count for 12 is 11, as worked out above.

Checking 208 by hand

Split the numbers from 1 to 250 into three groups and count each group by hand.

1. Numbers from 1 to 99. There are 9 one-digit numbers and 81 two-digit numbers that have different digits (the 9 two-digit numbers 11, 22, ..., 99 are removed from 90). Total: 90.

2. Numbers from 100 to 199. The first digit is 1. The second digit can be 0 or 2 to 9, which is 9 choices, since it cannot be 1. The third digit must differ from the second, which is 9 choices for each second digit. Total: 9 x 9 = 81.

3. Numbers from 200 to 250. The first digit is 2, and the second digit can be 0 to 5 because N has 5 there. The second digit cannot be 2. For each allowed second digit, count the third digits:

   • second digit 0: third digit 1 to 9 (200 is removed because 0 and 0 are equal). 9 numbers.
   • second digit 1: third digit is not 1, so 9 choices. 9 numbers.
   • second digit 2: not allowed. 0 numbers.
   • second digit 3: 9 numbers.
   • second digit 4: 9 numbers.
   • second digit 5: the number is tight, so the third digit can be 0 only, which gives 250. 1 number.

   Total: 9 + 9 + 0 + 9 + 9 + 1 = 37.

The total is 90 + 81 + 37 = 208, which is the value the program prints.

Step 4: remember answers for states that repeat

Only the free states repeat. Take a free state, meaning tight is false. Its answer depends only on the position, the previous digit and the started flag. It does not depend on which digits came before. So the first time the state is computed, the answer is saved in memo_, and later visits return the saved value.

A tight state is different. It is reached only along the path that matches N, so it is not reused. The code does not save tight answers, which is why the memo write is inside if (!tight).

The memo has one slot for each position, each previous digit from 0 to 9 plus the "no digit" value 10, and each value of started. For a number with 19 digits, that is 19 x 11 x 2 slots, and each slot takes at most 10 loop steps. That is a few thousand steps in total, however large N is.

Example 2: the same method for a digit sum

The previous example needed the previous digit. A different property needs a different state. Here the property is: the digits of the number add up to a target S. Examples: 5 has digit sum 5, and 104 has digit sum 1 + 0 + 4 = 5.

For a digit sum, the previous digit is not needed. The state is the position, the sum so far and tight. Leading zeros add 0 to the sum, so there is no need for a started flag.

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
 
// Count numbers in [0, N] whose digits add up to target.
class DigitSumCounter {
public:
    DigitSumCounter(std::uint64_t n, int target)
        : digits_(std::to_string(n)),
          target_(target),
          memo_(digits_.size() * 200, -1) {}
 
    std::int64_t count() { return go(0, 0, true); }
 
private:
    std::int64_t go(std::size_t pos, int sum, bool tight) {
        if (sum > target_) {
            return 0;  // too large already, no completion can fix it
        }
        if (pos == digits_.size()) {
            return sum == target_ ? 1 : 0;
        }
        std::size_t key = pos * 200 + static_cast<std::size_t>(sum);
        if (!tight && memo_[key] != -1) {
            return memo_[key];
        }
        int limit = tight ? digits_[pos] - '0' : 9;
        std::int64_t total = 0;
        for (int d = 0; d <= limit; ++d) {
            total += go(pos + 1, sum + d, tight && d == limit);
        }
        if (!tight) {
            memo_[key] = total;
        }
        return total;
    }
 
    std::string digits_;
    int target_;
    std::vector<std::int64_t> memo_;
};

A 19-digit number has a digit sum of at most 171, so 200 slots per position are enough for N up to 10^18. The check sum > target_ stops a path early when the sum is already too big.

Here is a check of the count for digit sum 5 in the numbers from 0 to 250. DigitSumCounter(250, 5).count() returns 15. The same 15 numbers can be listed by hand:

• 5 (one digit)
• 14, 23, 32, 41, 50 (two digits, the first digit from 1 to 5)
• 104, 113, 122, 131, 140 (1 followed by two digits that add to 4)
• 203, 212, 221, 230 (2 followed by two digits that add to 3, all at most 250)

That is 1 + 5 + 5 + 4 = 15. DigitSumCounter(250, 10).count() returns 24, and DigitSumCounter(100, 7).count() returns 8.

Example 3: counting a range

Often the question is "how many numbers from L to R". The trick is to count up to R, count up to L - 1, and subtract. The numbers from L to R are the numbers up to R with the numbers up to L - 1 removed.

The sample program already shows this. The numbers from 10 to 99 are counted as the count up to 99 (which is 90) minus the count up to 9 (which is 9). The result is 81, which the program printed.

The same idea works for the numbers from 100 to 199. The count up to 199 is 171, and the count up to 99 is 90. The difference is 81, which matches the hand count in the breakdown of 208 above.

Common mistakes

Saving answers for tight states

If the memo is used for tight states too, the program gives wrong answers. The tight state at a given position is stored, and then a later free path with a different upper bound reads that stored value. The output is wrong.

The only change is in the memo lines. The read becomes if (memo_[key] != -1) and the write becomes a plain memo_[key] = total; with no if (!tight) around it. The output is:

buggy count for N=99: 90 (correct is 90)
buggy count for N=250: 216 (correct is 208)
buggy count for N=1000: 819 (correct is 819)

The count for N=99 is right, but N=250 is off by 8. The bug only shows for some values of N, which is why the test cases should include numbers with several digits where the tight path changes.

Forgetting the started flag

If started is not tracked, the leading zeros count as real digits. The number 7 is then seen as 007, and the two zeros are equal neighbours. The number 7 is wrongly rejected, and the count is too small. For N = 250 it is 199 instead of 208.

The fix is the flag from Step 2. A leading zero must not change prev.

Counting the number 0

The base case returns 1 only if started is true. If the base case always returned 1, the number 0 would be counted in every answer. The count for N = 7 would then be 8, not 7.

Using 9 as the limit everywhere

The limit must be N's digit while tight is true. If 9 is used at every position, the program counts every number up to 99 for any N with two or more digits, and it does not stop at N. For N = 12 it would return 90 instead of 11.

A const object

The count method changes the memo, so it is not a const method. Calling it on a const object gives a compile error. This is the error from g++ 15 for the two lines const DigitCounter constant(5); and constant.count(); in a test file:

error: passing 'const DigitCounter' as 'this' argument discards qualifiers [-fpermissive]
   58 |     std::cout << constant.count() << '\n';
      |                  ~~~~~~~~~~~~~~^~
note:   in call to 'int64_t DigitCounter::count()'

The fix is to create a normal, non-const object, as the sample does. The error means the compiler is protecting the object from changes, and the memo is a change.

Practice

Exercise 1

Count the numbers from 1 to 30 that have no two neighbouring digits equal, by hand. Use the rule from this lesson.

Show the answer

The numbers 1 to 9 all count, which is 9. From 10 to 30 there are 21 numbers. Of these, 11 and 22 have equal neighbours. So 21 - 2 = 19 of them count. The total is 9 + 19 = 28.

Exercise 2

Using DigitCounter, how many numbers from 100 to 199 have no two neighbouring digits equal?

Show the answer

Count up to 199 and subtract the count up to 99. The count up to 199 is 171 and the count up to 99 is 90. The difference is 81.

Exercise 3

Using DigitSumCounter, how many numbers from 0 to 100 have digits that add up to 7?

Show the answer

DigitSumCounter(100, 7).count() returns 8. The numbers are 7 and the two-digit numbers 16, 25, 34, 43, 52, 61 and 70. The number 100 has a digit sum of 1, so it does not count.

Exercise 4

Why does the code not save the answer for a tight state in the memo? Explain it in plain words, and say what the wrong output was in the lesson.

Show the answer

A tight state is reached only along the path that matches N, so it is not reused by other paths. But the memo key holds only the position, the previous digit and started, so a saved tight answer can be read by a free path that has a different upper bound. In the lesson's test, saving tight answers gave 216 for N = 250, where the correct answer is 208.

Summary

• Digit DP walks the digits of N from left to right and builds numbers one digit at a time.
• The tight flag marks the path that matches N exactly. Once a digit is smaller than N's digit, the rest is free.
• The started flag stops leading zeros from counting as real digits.
• Only free states are saved in the memo, because a tight state is reached by one path only.
• The count for a range [L, R] is the count up to R minus the count up to L - 1.