Skip to content
Tutorials Center
My learning

Topics

Lesson 163 of 225 ยท Dynamic Programming

Digit DP

Learn digit DP in Python: count the numbers up to N whose digits satisfy a rule using position, tight flag and state, with memoization and worked examples.

How many integers from 1 to 10^18 have a digit sum of 40? How many numbers up to a billion contain no digit 4? How many have no two equal neighbouring digits? You cannot loop over 10^18 numbers, and a formula for each rule would be a different puzzle every time. Digit DP is the general tool: instead of visiting numbers, you build them one digit at a time from the most significant digit, and you count by the state of the digits chosen so far.

Because a number with L digits is built in L steps, the work depends on the number of digits (about 19 for a 64-bit value), not on the size of the range. Digit DP is a form of memoized recursion with a particular state shape. If you have seen bitmask DP or string DP, the idea of "state = a small summary of what we built so far" will feel familiar.

The core idea: counting up to N

Almost every digit DP problem is asked as "count numbers in [0, N] with property P". A range [A, B] is answered as count(B) - count(A - 1).

Write N as a string of digits, for example N = 2538. We fill positions left to right. At each position we may choose a digit from 0 to 9, but there is a catch: we must never exceed N.

  • As long as all digits chosen so far equal the prefix of N, the next digit is limited by N's digit at that position. We say we are tight.
  • As soon as we choose a digit smaller than N's digit, the rest is free: any digit 0..9 keeps us below N. We are no longer tight.

So the state is (position, tight, ...extra state about the digits so far). The extra state depends on the rule: the running digit sum, the previous digit, how many times a digit appeared, and so on.

flowchart TD
    A["pos 0, tight<br/>limit = 2"] --> B["digit 0 or 1<br/>not tight: free"]
    A --> C["digit 2<br/>still tight, limit = 5"]
    C --> D["digit 0..4<br/>not tight"]
    C --> E["digit 5<br/>still tight, limit = 3"]
    B --> F["rest: any digit<br/>10 choices per position"]

Choosing the leading digit of 2538: smaller digits release the limit, the equal digit keeps it.

Example 1: numbers with a given digit sum

Count the integers in [0, N] whose digits add up to exactly S.

Python Digit sum equals S

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Leading zeros are harmless here because a leading 0 adds nothing to the sum, so 009 counts as the number 9 exactly once. The number 0 itself is included in the range (it only matches when target is 0).

The number of states is positions x remaining x 2. For 19 digits, a target up to 171 and ten choices per state that is about 19 x 172 x 2 x 10, a few tens of thousands of operations. The recursion cache makes the 10^18 query instant.

Leading zeros and the "started" flag

Some rules treat a leading zero differently from a real zero. For "numbers with no digit 0", the number 105 is invalid but 5 is valid; yet when we build 5 as the 3-digit string 005 the leading zeros are not real digits. We therefore add a flag started (or leading) that becomes true once we place the first non-zero digit.

The same flag is needed for rules about the first digit, length, or the previous digit (a leading zero must not count as "previous digit 0").

Python Numbers with no two equal adjacent digits

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

prev = -1 means "no previous digit yet", so a first digit is always allowed. Compare the fast answer with the brute force on small n every time you write a digit DP; it is the quickest way to catch an off-by-one in the tight flag.

Ranges and negative edges

To count in [A, B], subtract: f(B) - f(A - 1). Be careful when A = 0; f(-1) should be treated as 0. If your function counts from 1 upward, f(0) = 0 already.

Python Counting in a range [A, B]

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Choosing the state

Digit DP problems differ only in what you remember. Some common choices:

Rule Extra state
Digit sum equals or divides something running sum (or remaining sum)
Divisible by k remainder of the number so far modulo k
No two adjacent equal digits previous digit
Contains a given digit exactly c times count so far
Non-decreasing digits previous digit
Contains a pattern like "13" small automaton state (see pattern matching)

Remember to keep the state small. A running sum bounded by 9 x 19 is tiny; a "set of used digits" is a 10-bit mask, which pairs nicely with bitmask DP for "all digits distinct".

Why the state count is small

The cache key is (pos, extra, started, tight). There are at most L positions, E values of extra state, and 2 x 2 flags, so at most 4 L E states, each doing up to 10 transitions. With L = 19 that stays far below what a naive loop over the range costs. Note the tight branch is visited only along a single path (the digits of N itself), so the real work is in the non-tight states.

Iterative form

The recursion is usually clear enough. The iterative version keeps a dictionary or array indexed by state and processes one digit at a time. It is a little longer, so use it only when recursion depth or speed matters. For 19 digits recursion depth is never an issue in Python.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the tight flag tell you while building a number digit by digit?

    While tight, the next digit can be at most N's digit at that position. Choosing a smaller digit releases the limit for all later positions.
  2. 2. How do you count the numbers in [A, B] with a digit-DP function f(n) that counts [0, n]?

    f(B) counts everything up to B and f(A - 1) counts everything below A, so the difference is exactly the numbers in the range.
  3. 3. Why do some digit DPs carry a started flag?

    A padded number like 005 should behave like 5. The flag makes leading zeros invisible to rules about zeros, the previous digit or the length.
  4. 4. Roughly how many states does a digit DP for a 19-digit limit with a digit sum up to 171 have?

    States are position x running sum x flags. That is a few thousand, each with up to ten transitions, regardless of how large N is.

Summary

  • Digit DP counts numbers up to N with a digit property by building them left to right.
  • The state is (position, tight, extra summary of the digits so far); add started when leading zeros matter.
  • While tight, the next digit is capped by N's digit; a smaller digit makes everything after it free.
  • Range answers are f(B) - f(A - 1).
  • Choose the smallest extra state that decides the rule: sum, remainder, previous digit, a count, or a bitmask of used digits.
  • Always cross-check against brute force on small inputs.

Next: Egg Dropping, Rod Cutting and Classic DP Puzzles, a tour of well-known DP problems.