DP Dynamic programming Technique

Digit DP

Also known as: Digit DP · digit dynamic programming · lucky tickets · counting numbers in a range · numbers with a condition on digits · tight

How many numbers from L to R have a property that is checked digit by digit: a sum, neighbouring digits, a remainder. Trying the numbers costs R − L, while a pass over the digits of R with a table of “how many ways to finish” takes dozens of operations even for 10¹⁸.

Expert 20 minutes dynamic programming counting number theory binary search contests

Complexity

Time: O(D · 10 · S)
Memory: O(D · S)

D is the number of digits, S the number of states that must be remembered about the digits already placed (a sum, a remainder, the previous digit). It does not depend on the size of the numbers: 10¹⁸ is 18 digits.

Know first

Dynamic programming Binary search

In the base course

22. Remember instead of recomputing

Where it runs

counting numbers in a huge range by a condition on digits: sums, bans, divisibility
the k-th number with such a property, by binary search on the count or by descending over the digits
numbering without forbidden numbers: floors, flats, tickets
olympiads: numbers divisible by their digit sum, numbers without repeated neighbouring digits

A six-digit ticket is lucky if the sum of its first three digits equals the sum of its last three. Out of a million numbers, 55,252 are lucky, about one in eighteen. There are exactly as many six-digit strings with digit sum 27, and that is no coincidence. How many lucky ones there are among the numbers up to yours can be found without trying the numbers: it is enough to walk along the six digits of your number and take one number from a small table at each. The same pass counts lucky tickets of eighteen digits, which have 10¹⁸ numbers.

For the ticket 123456 the next lucky one is 123501, and up to it there are 5541 lucky tickets. Among the numbers from 700000 to 700999 only 36 are lucky: the left half is the same throughout this thousand, 700 with sum 7, and there are exactly 36 right halves with sum 7.

The idea

Brute force checks each number. Digit DP counts numbers in batches. Take a number x and walk along its digits from the left. In the first position one can put a digit smaller than the first digit of x, and then all numbers with this beginning are certainly smaller than x, while the other digits are arbitrary. How many of them are lucky depends only on what has already been placed: on the sum of the digits placed. That number is taken from a table. Or one can put the first digit of x itself, and then go to the second position “tight”, and everything repeats.

The number of good numbers from 0 to x is a sum over positions: for each digit d smaller than x's digit at this position, the number of good endings for the beginning “the digits of x up to this position, then d”. This depends only on a short state, such as a sum, a remainder or the previous digit, and is computed in advance by a table. The answer for a range [L, R] is the difference of the answers for R and L − 1.

For lucky tickets the table is ways[r][b]: in how many ways r digits with sum b can be written. It is built like a knapsack: ways[r][b] is the sum of ways[r − 1][b − d] over the digit d from 0 to 9. The number of triples of digits with sum s is c_s = ways[3][s], and a lucky ticket is two triples with one sum, so there are Σ c_s² = 55,252 lucky tickets in all.

Each number y < x of the same length falls into exactly one branch of the pass: at the first position where the digits of y and x differ, the digit of y is smaller, and y is counted in the branch of this position and this digit.

Numbers of one length compare as strings: y < x exactly when at the first position i where they differ, the digit of y is smaller. Up to position i the digits of y coincide with those of x, which is the “tight” path; at position i there is d < x_i, and after it any digits: that is how the branch (i, d) is made. y cannot fall into another branch: that one has either a different first position of difference or a different digit there. x itself is checked separately, at the end of the path.

There are as many lucky six-digit tickets as six-digit strings with digit sum 27.

Replace each digit d of the ticket's right half with 9 − d. This is a one-to-one map of strings to strings: applied twice, it returns the original. The sum b of the right half becomes 27 − b. A ticket is lucky when the sum a of the left half equals b, that is, when in the new string the digit sum a + 27 − b = 27.

Code

The table ways is built once. lucky_up_to(x, n) walks along the 2n digits of x: in the left half, the branch of digit d leaves a few more digits of the left half and the whole right half free, and it has as many lucky tickets as there are pairs “an ending of the left half with sum t, a right half with sum (placed so far + d + t)”. In the right half, a branch has to bring the difference down to zero, and that is one number from the table. The next lucky ticket is a binary search on the count.

The numbers 10, 670, 55,252, 4,816,030, … are how many lucky tickets there are of 2, 4, 6, 8 digits. There are 10¹⁸ tickets of eighteen digits, and 32,458,256,583,753,952 of them are lucky, about 3.2 %: the longer the halves, the less often their sums coincide.

What it costs

A pass over the digits is D positions of 10 digits each, with one or two table lookups at each; the table is D × 9D numbers. Brute force grows with the number of numbers.

Brute force in Python goes through a million numbers in almost two seconds, the pass over digits in tenths of a millisecond. For 10¹⁸ numbers counting by digits takes about a millisecond, while brute force would take tens of thousands of years.

Where it is easy to go wrong

An inclusive bound. The pass counts numbers strictly smaller than x; x itself must be checked separately. Otherwise the answer for [L, R] loses R.
L − 1 when L = 0. The count up to −1 is zero, not a pass over the digits of −1.
Leading zeros. For tickets they matter: 000001 is a ticket too. For ordinary numbers they do not: if the condition concerns “neighbouring digits”, the number 7 does not begin with zeros, and the state “nothing placed yet” is needed separately.
Too poor a state. A branch must know everything on which the goodness of the endings depends: for tickets, the difference of the sums; for a ban on “13”, whether the previous digit was a one. A forgotten feature gives a confident wrong answer.
Overflow. There are 3.2 · 10¹⁶ lucky 18-digit tickets, which fits in 64 bits, but the products in intermediate sums are better checked in advance.

Where it is used

Any count of “how many numbers from L to R are such that…”, if the property is checked from left to right with little memory: the sum or product of digits, forbidden combinations, divisibility (a remainder is a state too), numbers divisible by the sum of their digits. With binary search on the count, the k-th such number: for example, the number on a lift button if numbers with a four and with “13” are skipped. The same technique works in other bases and for strings with bans: it is counting paths in an automaton that reads digits.

Problems

Lucky tickets of 2n digits in ranges of numbers. And a lift without fours and the thirteenth: what number is on the button of the N-th floor.

Lucky in a range A lift without fours