# Counting without enumerating

> How many numbers between A and B have some property in their digits? Digit DP answers without looking at them one by one.

- Author: Marcello Oliveira (https://mrcll.me/about/)
- Published: Oct 31, 2026
- Topics: ICPC, Fundamentals
- URL: https://mrcll.me/stories/digit-dp/

How many numbers up to 1,000 have no digit 4 and never contain “13”? You could check all thousand. The answer is 712, and you can get it by visiting 9 states.

First, a range is two prefixes: the count for [A, B] is the count for [0, B] minus the count for [0, A−1]. So you only ever count from zero up to some N.

Inside [0, N], build the number from its most significant digit and carry one flag, tight, which says whether you are still pressed against the limit. If N is 723 and you put a 7 first, the next digit can only go up to 2. Put a 6 first and you are free: anything from 0 to 9 works from there on.

> Interactive figure (DigitDP): open the web version at https://mrcll.me/stories/digit-dp/

Why does memoization pay off? Think of an 18-digit number that ends in 0123456789. Every possible prefix in front of that ending leads to the same question about the same remaining digits, 10⁸ identical calculations if you recompute it each time. Store it once and look it up.

The state stays small: the position, whatever the question needs to remember (here, whether the last digit was a 1), and tight. The count of states depends on how many digits N has, not on how big N is. Before you enumerate anything, ask what the smallest state is that sums up everything that came before.