Get started

Digit DP Coding Problems: 1 Question with Solutions

1 digit dp coding problem — 1 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 1-day plan.

  • Problems: 1
  • By difficulty: 1 hard
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

Digit DP counts the integers in a range that have some property of their digits — how many contain a 1, how many have no repeated digit, how many have a digit sum divisible by k — without visiting them one by one. It chooses the digits from the most significant end, remembering whether the number so far still matches the upper bound digit for digit, plus whatever the property needs; ranges up to 10¹⁸ then come down to a few thousand states. The problems here practise that state and the counting it supports.

How digit dp works, step by step

N213S = 4count = 11(pos, sum, tight)(0, 0, tight)(1, 2, tight)(2, 3, tight)(3, 6, tight)0 → +51 → +42 → tight0 → +11 → tight0 → +01 → +12 → +03 → tight6 ≠ 4 → +0free[k][r]: k free digits with sum rr=0r=1r=2r=3r=4k=010000k=111111k=212345
Counting numbers up to N with a given digit sum, with digit DP. Example: N = 213, S = 4: how many x in [0, 213] have digit sum 4?
  1. Count the numbers from 0 to 213 whose digits sum to 4. Build each one digit by digit from the left, as a state (position, sum so far, tight): tight means the prefix still equals 213's, so the next digit may not exceed 213's digit there.
  2. Once a digit goes below 213's, the rest is free: any digits at all. So precompute free[k][r], the ways k free digits can sum to r, by adding the last digit: free[k][r] = free[k−1][r] + free[k−1][r−1] + … + free[k−1][r−9].
  3. At position 0 (sum 0, tight), choose 0, below 213's 2: the number is no longer tight, and its 2 remaining digits must sum to 4 − 0 − 0 = 4. free[2][4] = 5 (004, 013, 022, 031, 040).
  4. At position 0 (sum 0, tight), choose 1, below 213's 2: the number is no longer tight, and its 2 remaining digits must sum to 4 − 0 − 1 = 3. free[2][3] = 4 (103, 112, 121, 130).
  5. Choosing 2, 213's own digit, keeps the number tight: the next position is still capped. The state becomes (position 1, sum 2, tight).
  6. At position 1 (sum 2, tight), choose 0, below 213's 1: the number is no longer tight, and its 1 remaining digit must sum to 4 − 2 − 0 = 2. free[1][2] = 1 (202).
  7. Choosing 1, 213's own digit, keeps the number tight: the next position is still capped. The state becomes (position 2, sum 3, tight).
  8. At position 2 (sum 3, tight), digits 0 to 2 finish the number: 0 needs 1 more with no digits left, impossible; 1 needs 0 more with no digits left, which works; 2 overshoots 4. That adds 1 (211).
  9. Choosing 3, 213's own digit, keeps the number tight to the very end: it is 213 itself, whose digit sum is 6, not 4, so it adds 0.
  10. count = 11: 4, 13, 22, 31, 40, 103, 112, 121, 130, 202, 211. Only one state per position stays tight and every free branch is a table lookup, so the work is O(digits × S × 10) instead of checking all 214 numbers.

Digit DP study plan

The one Digit DP problem (1 hard) over 1 day, about 1 h 5 min in all — the pattern first, then easiest to hardest. Then move on to Game Theory.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve this problem.

Next topic: Game Theory

Digit DP: the essentials

When to reach for it

"How many integers from 1 to n" (or in [low, high]) have a property of their digits: contain a 7, repeat no digit, have a digit sum divisible by k — or how often digit d is written. With n up to 10¹⁸ testing each is hopeless, but n has at most 19 digits. A range is count(high) - count(low - 1).

The pattern

It is Dynamic Programming over the digits of n, chosen from the most significant end. The state is the position, a tight flag — true while every digit so far equals n's, so the next may not exceed n's digit there — and whatever the property needs: a count, a sum modulo k, a mask of digits used, whether the number has started. Memoise on that state.

from functools import cache

def count_digit_one(n):                 # 1s written across 0..n
    s = str(n)
    @cache
    def go(i, tight, ones):             # s[:i] decided; tight: equal to n so far
        if i == len(s):
            return ones
        top = int(s[i]) if tight else 9
        return sum(go(i + 1, tight and d == top, ones + (d == 1)) for d in range(top + 1))
    return go(0, True, 0)

Cost

States × choices: positions × 2 for the flag × the property's own range, with up to 10 digits tried from each state. Counting ones up to 10⁹ takes a few hundred states and a few thousand steps; looping over the numbers takes a billion.

Common mistakes

  • Letting the next digit run to 9 while the prefix is still tight, which counts numbers above n.
  • Leading zeros: 007 is 7, so for "no repeated digit" its zeros must not count; carry a started flag.
  • count(high) - count(low) for an inclusive range, which drops low itself.
  • A memo array shared across different n: tight states depend on n's digits, so clear it, or cache only the states that are not tight.

Start with

All digit dp problems

Hard (1)

Companies that ask digit dp problems

Next topic: Game Theory