Digit DP — Count Numbers with Digit Constraints

Digit DP Pattern

Build numbers digit by digit. The key flag is "tight": are we still bounded by the upper limit N? If tight, the next digit can only go up to N's digit at that position. If not tight, any digit 0-9 is allowed.

Common problems: count numbers with digit sum = K, numbers without repeated digits, numbers with at most K distinct digits, etc.

State Template

solve(pos, tight, ...extra_state):
  if pos == numDigits: return baseCase
  if memo[pos][tight][...]: return cached
  limit = tight ? digits[pos] : 9
  for d = 0 to limit:
    newTight = tight && (d == limit)
    ans += solve(pos+1, newTight, ...)
  return memo[pos][tight][...] = ans

State Variable	Purpose	Range
pos	Current digit position (left to right)	0 to D-1
tight	Are we still bounded by N?	0 or 1
started	Have we placed a non-zero digit yet? (for leading zeros)	0 or 1
...extra	Problem-specific: digit sum, last digit, count of X, etc.	varies

C++ — Digit DP Template (Count numbers ≤ N with digit sum = S)

string num;
int memo[20][2][200]; // [pos][tight][digitSum]

int solve(int pos, bool tight, int sum) {
    if (pos == num.size())
        return sum == targetSum ? 1 : 0;
    if (memo[pos][tight][sum] != -1)
        return memo[pos][tight][sum];

    int limit = tight ? (num[pos] - '0') : 9;
    int ans = 0;

    for (int d = 0; d <= limit; d++) {
        ans += solve(pos + 1,
            tight && (d == limit),
            sum + d);
    }
    return memo[pos][tight][sum] = ans;
}

int countUpTo(int N) {
    num = to_string(N);
    memset(memo, -1, sizeof(memo));
    return solve(0, true, 0);
}

Complexity

Time

O(D × 10 × S)

D = digits, 10 choices per digit, S = state space.

Space

O(D × S)

Memoization table.

Key Trick

f(L,R) = f(R) - f(L-1)

Count in [L,R] = countUpTo(R) - countUpTo(L-1).

Handles

N ≤ 10^18

Only ~18 digits, polynomial in D.

📝 Notes

▼