Digit DP: Counting Numbers With Constraints

What This Concept Is

Digit DP counts bounded integers by processing their decimal digits. For a fixed bound N with D digits, represent every candidate with exactly D digits, allowing left padding by zeros. A tight flag records whether the chosen prefix still equals N's prefix; only then is the next digit bounded by N's next digit.

The lab counts digit sum exactly S in [0,N]. State (position,sum,tight) suffices because padded zeros do not change digit sum. The number zero is included once and has digit sum zero. Define F(-1,S)=0; a nonnegative range [L,R] then has count F(R,S)-F(L-1,S).

Why It Matters Here

Leading zeros, tightness and cache lifetime are independent concerns. A started flag is necessary only when padding changes the property, such as "contains digit 0" or "no equal adjacent significant digits". Adding or removing it without specifying zero's representation can silently count the wrong objects.

Concrete Examples

For N=25 and S=3, valid integers are 3,12,21. The two-digit representations are 03,12,21. Prefix 0 is below bound prefix 2 and permits any next digit; prefix 1 does too; prefix 2 remains tight and permits only 0..5. Count is 3. For [10,25], subtract F(9,3)=1 and obtain 2.

Transition from sum s with chosen digit d gives sum s+d and next_tight = tight and (d == bound_digit). Discard sums greater than S. At position D, contribute one iff sum=S. Initial state (0,0,true) counts one empty prefix. Every D-digit padded representation follows one unique path, so addition counts numbers without duplication.

Tight cache states are valid. Inside a function closed over one fixed N and S, memoizing (position,sum,tight) is correct, including tight=true. Reusing that cache for a different bound without including or resetting N is incorrect. Loose-state reuse across queries also needs compatible remaining length and constraint semantics. A rolling tabulation avoids a recursive stack and is a valid alternative, as implemented in the lab.

When started matters. To count numbers containing a zero digit, padded 007 must not make 7 qualify. Track whether a significant digit has started and whether a significant zero appeared. Decide separately whether integer zero, represented canonically as "0", qualifies at the terminal state.

Common Confusion / Misconceptions

Setting tight to (d==bound_digit) without the old flag can wrongly re-tighten an already smaller prefix. Digit sum zero includes integer zero under this contract; positive-only counting must subtract it when appropriate. No universal digit-state template automatically solves a new property: the extra coordinates still need a sufficiency argument and resource bound.

How To Use It

Specify the counted objects, inclusive range and zero behavior. Define states for exactly the constraints required. For sum S, there are at most 2*(min(S,9D)+1) states per layer, each trying at most ten digits, hence O(D10(min(S,9D)+1)) arithmetic work and O(D+min(S,9D)+1) storage including the bound's digits. Large counts require growing integers. Reset per-query state and compare every small bound against enumeration.

Check Yourself

Why is no started flag needed for digit sum? When can tight states be cached? How should a range beginning at zero use F(-1,S)?

Mini Drill or Application

Count sum 1 through 100, sum 0 through 100, and sum 19 through 99. Feedback: 3 (1,10,100), 1 (0), and 0. Then explain how the answer would change if only positive numbers were counted.

Read This Only If Stuck

Competitive Programming: bounded digit-counting exercises, if present in your edition. The complete derivation above and Lab E are sufficient for the core; no guessed book section is required.