Digit DP

Count numbers up to N that satisfy a digit property by building them one digit at a time, with a tight flag that tracks whether the prefix still matches N.

40 minCF 1900–24005 interactive10 problems

The problem

Count how many integers in $[a, b]$ have a property that depends on their digits. For example: no two adjacent digits are equal (1213 yes, 1223 no).

The range can reach $10^{18}$ , so you cannot test each number. Brute force over $10^{18}$ numbers is far out of reach.

1 of 8