SyntaxPilot
Courses/Competitive Programming/Lesson 37

Competitive Programming · Lesson 37 of 90 · 10 min

DP 6: digit DP

queued

These are the notes for Competitive Programming episode 37, part six of the dynamic programming section. Meera, a bus conductor, hands out tickets numbered L to R, and a ticket is "lucky" when its digit sum is a multiple of K. An original problem, Lucky Tickets, asks how many lucky tickets a roll holds, with R up to 10^18. Looping over the range is right but gets TLE at R = 10^12. Two observations solve it: count(R) − count(L − 1) turns a range into two prefixes, and a number can be built digit by digit from the left, remembering only the position, the digit sum modulo K, and whether we are still equal to R's digits (the tight flag). That state, dp(pos, rem, tight), has about 19 · 100 · 2 values. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

Every morning Meera gets a roll of bus tickets numbered L to R. Passengers like a ticket whose digits add up to a multiple of K: with K = 10, ticket 19 is lucky (1 + 9 = 10), ticket 46 is lucky, ticket 47 is not. The depot asks how many lucky tickets a roll holds. Rolls can be numbered up to 10^18, so nobody can check the tickets one by one.

Problem N · Lucky Tickets

(Written for this course, in the style of an AtCoder Beginner Contest problem.)

Count the integers x with L ≤ x ≤ R whose digit sum is a multiple of K.

  • Input: one line L R K (1 ≤ L ≤ R ≤ 10^18, 1 ≤ K ≤ 100).
  • Output: the count.
Input Output Why
1 100 10 9 19, 28, 37, 46, 55, 64, 73, 82, 91
1 1000000000000000000 7 142857142856594041 about one number in seven
7 7 7 1 7 is a multiple of 7
123456789 987654321012 13 75963926232 a wide range

A range of 10^18 numbers is a hint: the answer can't come from looking at numbers, only from looking at digits.

Attempt 1: loop over every ticket (Time Limit Exceeded)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ll L, R;
    int K;
    cin >> L >> R >> K;
    ll cnt = 0;
    for (ll x = L; x <= R; x++) {           // every ticket
        int sum = 0;
        for (ll y = x; y > 0; y /= 10) sum += y % 10;
        if (sum % K == 0) cnt++;
    }
    cout << cnt << "\n";
    return 0;
}

1 100 10 prints 9 (correct). 1 1000000000000 7 gets Time Limit Exceeded: a trillion numbers, and 10^18 is a million times more.

Step 1: count from zero

A range with two ends is awkward; a range that starts at 0 is easy. Like prefix sums (episode 7):

lucky in [L, R] = lucky in [0, R] − lucky in [0, L − 1]

So we need one function, countUpTo(x) = how many lucky numbers lie in [0, x]. (0 has digit sum 0, so it is counted, but it cancels in the subtraction.)

Step 2: build the number, slot by slot

Write x as a string of digits, for example R = 472. Fill three slots from the left, like filling the amount boxes on a cheque.

  • To know whether the finished number is lucky we only need the digit sum so far, modulo K, not the digits themselves.
  • The number must stay ≤ R. While every digit so far equals R's digit, the next digit is capped by R's digit. As soon as one digit is smaller, the number is already smaller than R and every later slot is free (0 to 9).
slot 1 2 3
R 4 7 2
we pick 4 3 0–9
tight? yes (4 = 4) no (3 < 7) no

That yes/no is the tight flag: "is the prefix written so far equal to R's prefix?"

The digit DP checklist

  1. State: go(pos, rem, tight) = the number of ways to fill slots pos, pos + 1, … so that the total digit sum is ≡ 0 (mod K), given the remainder rem of the digits already written and the flag tight.
  2. Transition: try every digit d from 0 to lim, where lim = tight ? R's digit : 9; the next state is go(pos + 1, (rem + d) % K, tight && d == lim).
  3. Base: pos == length → return 1 if rem == 0, else 0.
  4. Memo: only the states with tight == false. A tight state occurs once per position (along R's own digits); the free states repeat many times.
  5. Answer: countUpTo(R) − countUpTo(L − 1).

Leading zeros are harmless here: 007 has the same digit sum as 7, so numbers with fewer digits are counted correctly as zero-padded strings.

The accepted solution

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

string s;
int K;
ll memo[20][100];

// ways to fill digits pos.. so the digit sum is a multiple of K
ll go(int pos, int rem, bool tight) {
    if (pos == (int)s.size()) return rem == 0;
    if (!tight && memo[pos][rem] != -1) return memo[pos][rem];
    int lim = tight ? s[pos] - '0' : 9;     // glued to R? then at most R's digit
    ll res = 0;
    for (int d = 0; d <= lim; d++)
        res += go(pos + 1, (rem + d) % K, tight && d == lim);
    if (!tight) memo[pos][rem] = res;
    return res;
}

ll countUpTo(ll x) {                       // lucky numbers in [0, x]
    if (x < 0) return 0;
    s = to_string(x);
    memset(memo, -1, sizeof memo);
    return go(0, 0, true);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll L, R;
    cin >> L >> R >> K;
    cout << countUpTo(R) - countUpTo(L - 1) << "\n";
    return 0;
}
Input Output
1 100 10 9
1 1000000000000000000 7 142857142856594041 (instant)
7 7 7 1
123456789 987654321012 13 75963926232

A stress test

brute loops over the range; the digit DP must agree on 1000 random ranges (L, R ≤ 6000) and random K ≤ 30.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

string s;
int K;
ll memo[20][100];

// ways to fill digits pos.. so the digit sum is a multiple of K
ll go(int pos, int rem, bool tight) {
    if (pos == (int)s.size()) return rem == 0;
    if (!tight && memo[pos][rem] != -1) return memo[pos][rem];
    int lim = tight ? s[pos] - '0' : 9;     // glued to R? then at most R's digit
    ll res = 0;
    for (int d = 0; d <= lim; d++)
        res += go(pos + 1, (rem + d) % K, tight && d == lim);
    if (!tight) memo[pos][rem] = res;
    return res;
}

ll countUpTo(ll x) {                       // lucky numbers in [0, x]
    if (x < 0) return 0;
    s = to_string(x);
    memset(memo, -1, sizeof memo);
    return go(0, 0, true);
}

ll brute(ll L, ll R) {
    ll c = 0;
    for (ll x = L; x <= R; x++) {
        int sum = 0;
        for (ll y = x; y > 0; y /= 10) sum += y % 10;
        if (sum % K == 0) c++;
    }
    return c;
}

int main() {
    mt19937 rng(37);
    for (int t = 1; t <= 1000; t++) {
        ll L = rng() % 3000 + 1, R = L + rng() % 3000;
        K = rng() % 30 + 1;
        ll fast = countUpTo(R) - countUpTo(L - 1);
        if (brute(L, R) != fast) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 1000 tests passed";
}

Output: all 1000 tests passed.

A second shape: leading zeros matter

New rule: count x in [0, N] with no two equal neighbouring digits (1100 is bad, 1210 is good). Now the state needs the previous digit instead of a remainder: (pos, prev, tight). But when N = 100 has three digits, the number 7 is built as 0 0 7, and those two zeros look like equal neighbours.

Without a "nothing written yet" state:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

string s;
ll memo[20][11];

// prev = 10 means: no digit written yet (only leading zeros so far)
ll go(int pos, int prev, bool tight) {
    if (pos == (int)s.size()) return 1;
    if (!tight && memo[pos][prev] != -1) return memo[pos][prev];
    int lim = tight ? s[pos] - '0' : 9;
    ll res = 0;
    for (int d = 0; d <= lim; d++) {
        if (d == prev) continue;                 // same as its neighbour
        int np = d;                              // every digit counts?
        res += go(pos + 1, np, tight && d == lim);
    }
    if (!tight) memo[pos][prev] = res;
    return res;
}

int main() {
    ll N;
    cin >> N;
    s = to_string(N);
    memset(memo, -1, sizeof memo);
    cout << go(0, 10, true) << "\n";       // numbers 0..N
    return 0;
}

N = 100 prints 81 (expected 91): all ten one-digit numbers (000 … 009) are rejected.

The fix: prev = 10 means "no digit written yet"; a leading zero keeps it at 10.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

string s;
ll memo[20][11];

// prev = 10 means: no digit written yet (only leading zeros so far)
ll go(int pos, int prev, bool tight) {
    if (pos == (int)s.size()) return 1;
    if (!tight && memo[pos][prev] != -1) return memo[pos][prev];
    int lim = tight ? s[pos] - '0' : 9;
    ll res = 0;
    for (int d = 0; d <= lim; d++) {
        if (d == prev) continue;                 // same as its neighbour
        int np = (prev == 10 && d == 0) ? 10 : d; // a leading zero writes nothing
        res += go(pos + 1, np, tight && d == lim);
    }
    if (!tight) memo[pos][prev] = res;
    return res;
}

int main() {
    ll N;
    cin >> N;
    s = to_string(N);
    memset(memo, -1, sizeof memo);
    cout << go(0, 10, true) << "\n";       // numbers 0..N
    return 0;
}

N = 100 prints 91 (0 … 9 are ten numbers, 10 … 99 with different digits are 9 · 9 = 81, and 100 has 00).

Complexity vs the constraints

Approach Time Verdict
loop over [L, R] O((R − L) · 19) TLE at R = 10^12
digit DP O(digits · K · 2 · 10) ≈ 19 · 100 · 2 · 10 = 38 000 per call accepted

The cost depends on the number of digits (log₁₀ R), not on the value of R.

Common mistakes (and the real outputs)

Bug 1: no tight limit

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

string s;
int K;
ll memo[20][100];

// ways to fill digits pos.. so the digit sum is a multiple of K
ll go(int pos, int rem, bool tight) {
    if (pos == (int)s.size()) return rem == 0;
    if (!tight && memo[pos][rem] != -1) return memo[pos][rem];
    int lim = 9;                            // any digit?
    ll res = 0;
    for (int d = 0; d <= lim; d++)
        res += go(pos + 1, (rem + d) % K, tight && d == lim);
    if (!tight) memo[pos][rem] = res;
    return res;
}

ll countUpTo(ll x) {                       // lucky numbers in [0, x]
    if (x < 0) return 0;
    s = to_string(x);
    memset(memo, -1, sizeof memo);
    return go(0, 0, true);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll L, R;
    cin >> L >> R >> K;
    cout << countUpTo(R) - countUpTo(L - 1) << "\n";
    return 0;
}

1 100 10 prints 99 (expected 9). With three free slots it counted every lucky number up to 999 (100 of them, minus the one in [0, 0]).

Bug 2: the memo is not reset between the two calls

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

string s;
int K;
ll memo[20][100];

// ways to fill digits pos.. so the digit sum is a multiple of K
ll go(int pos, int rem, bool tight) {
    if (pos == (int)s.size()) return rem == 0;
    if (!tight && memo[pos][rem] != -1) return memo[pos][rem];
    int lim = tight ? s[pos] - '0' : 9;     // glued to R? then at most R's digit
    ll res = 0;
    for (int d = 0; d <= lim; d++)
        res += go(pos + 1, (rem + d) % K, tight && d == lim);
    if (!tight) memo[pos][rem] = res;
    return res;
}

ll countUpTo(ll x) {                       // lucky numbers in [0, x]
    if (x < 0) return 0;
    s = to_string(x);
    return go(0, 0, true);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(memo, -1, sizeof memo);           // once, at the start
    ll L, R;
    cin >> L >> R >> K;
    cout << countUpTo(R) - countUpTo(L - 1) << "\n";
    return 0;
}

50 100 10 prints -4 (expected 5: 55, 64, 73, 82, 91). The memo was filled while counting up to 100 (3 digits), where position 1 means "2 slots left". For 49 (2 digits) position 1 means "1 slot left", so the stored answers are wrong. Reset the memo per call, or index the memo by slots remaining instead of position (then it can be shared).

Bug 3: count(L) instead of count(L − 1)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

string s;
int K;
ll memo[20][100];

// ways to fill digits pos.. so the digit sum is a multiple of K
ll go(int pos, int rem, bool tight) {
    if (pos == (int)s.size()) return rem == 0;
    if (!tight && memo[pos][rem] != -1) return memo[pos][rem];
    int lim = tight ? s[pos] - '0' : 9;     // glued to R? then at most R's digit
    ll res = 0;
    for (int d = 0; d <= lim; d++)
        res += go(pos + 1, (rem + d) % K, tight && d == lim);
    if (!tight) memo[pos][rem] = res;
    return res;
}

ll countUpTo(ll x) {                       // lucky numbers in [0, x]
    if (x < 0) return 0;
    s = to_string(x);
    memset(memo, -1, sizeof memo);
    return go(0, 0, true);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll L, R;
    cin >> L >> R >> K;
    cout << countUpTo(R) - countUpTo(L) << "\n";
    return 0;
}

19 100 10 prints 8 (expected 9): ticket 19 itself is lucky and was subtracted away.

Summary table

Mistake What you see Why Fix
int lim = 9; (no tight) 99 instead of 9 counts numbers above R lim = tight ? s[pos] - '0' : 9
memset once in main -4 instead of 5 position means something else for a shorter number reset per call (or index by slots left)
count(R) − count(L) 8 instead of 9 L itself is dropped count(R) − count(L − 1)
leading zero treated as digit 0 81 instead of 91 007 is not "0 then 0 then 7" a "not started" state (prev = 10)
int result overflow above ~2.1 · 10^9 counts reach 10^18 long long
memoising tight states with free ones wrong counts a tight state's answer differs memo only !tight (or add tight to the memo key)

Mini project

Build a "number counter" toolkit: a function countUpTo(x) that takes a predicate in the form of a small state machine (start, step(state, digit), accept(state)) and runs a generic digit DP over (pos, state, tight, started). Use it for three properties: digit sum divisible by K, no equal neighbours, and "contains the digits 4 and 7 at least once each". Check each against a brute force for all ranges up to 5000.

Practice

  1. Count numbers ≤ N with exactly k non-zero digits (N ≤ 10^18, k ≤ 3).

    Answer State (pos, count of non-zero digits so far, tight); stop counting above k. For N = 100, k = 1: <b>19</b> (1 … 9, 10, 20, …, 90, 100).

  2. Sum of digit sums from L to R (mod 10^9 + 7).

    Answer Return a pair (count, sum) from each state: adding digit d adds d · count to the sum. Or keep the running sum in the state (at most 9 · 19 = 171). For 1 … 10 the answer is <b>46</b> (45 + 1).

  3. Numbers in [L, R] divisible by their own digit sum.

    Answer Try every target sum S from 1 to 162 separately: state (pos, digit sum so far ≤ S, value mod S, tight); accept when the sum is exactly S and the value mod S is 0. Summed over all S that is about 19 · 10 · Σ S² ≈ 3 · 10^8 simple steps: fine in C++. For 1 … 20 the answer is <b>13</b> (1–9, 10, 12, 18, 20).

  4. "No equal neighbours" on a range [L, R].

    Answer count(R) − count(L − 1) with the second program of this episode. For [10, 100]: 91 − 10 = <b>81</b>.

Quick quiz

Counting numbers ≤ 472. You wrote 4, then 5. What can the last digit be?

A) only 0, 1 or 2 · B) any digit 0 to 9 · C) nothing: 45_ > 472 · D) only 0 to 7

Answer

B. 5 < 7, so 45_ is already below 47_: the tight flag is now false and the last slot is free (450 … 459).

Interview questions

  1. When do you think of digit DP? When you must count (or sum over) numbers up to a huge bound (10^18) with a property that depends on their digits.
  2. What is the tight flag? Whether the prefix built so far equals the bound's prefix; it caps the next digit at the bound's digit.
  3. Why memoise only non-tight states? A tight state appears once per position; its answer differs from the free state with the same (pos, rem), so it must not share the memo entry.
  4. How do you handle a range [L, R]? count(R) − count(L − 1).
  5. When do leading zeros matter? When the property looks at digit positions or neighbours (no equal neighbours, first digit, number of digits); then add a "started" state.
  6. What is the complexity? O(digits · states · 10), independent of the bound's value.

Glossary

Term Meaning Example
Digit DP DP that builds a number digit by digit to count numbers with a property dp(pos, rem, tight)
Digit sum The sum of a number's decimal digits 472 → 13
Prefix count count(x) = how many valid numbers lie in [0, x] count(R) − count(L − 1)
Position (pos) Which digit slot we are filling, from the left 0, 1, 2 for 472
Remainder (rem) The digit sum so far, modulo K 4 + 7 = 11 → 1 (mod 10)
Tight flag The prefix so far equals the bound's prefix 4_ _ for R = 472
Free state A state with tight = false: any digit 0–9 next 43_
Leading zeros Zeros before the first non-zero digit when padding 007
"Not started" state A state meaning no real digit has been written yet prev = 10
Memoisation Storing a function's answers so each state is computed once memo[pos][rem]
Stress test Fast vs brute force on random small tests all 1000 tests passed

Summary

  • Looping over [L, R] is hopeless for 10^18; count digits, not numbers.
  • Answer = count(R) − count(L − 1).
  • Build numbers from the left; the state is (pos, what the property needs, tight). lim = tight ? R's digit : 9.
  • Memoise only the free (non-tight) states, and reset the memo per call when it is indexed by position.
  • Leading zeros: add a "not started" state when the property looks at positions or neighbours.
  • Real bugs: no tight (99), memo not reset (-4), count(L) (8), leading zeros as digits (81).

Solutions in C++, Java and Python

Problem N · Lucky Tickets

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

string s;
int K;
ll memo[20][100];

// ways to fill digits pos.. so the digit sum is a multiple of K
ll go(int pos, int rem, bool tight) {
    if (pos == (int)s.size()) return rem == 0;
    if (!tight && memo[pos][rem] != -1) return memo[pos][rem];
    int lim = tight ? s[pos] - '0' : 9;     // glued to R? then at most R's digit
    ll res = 0;
    for (int d = 0; d <= lim; d++)
        res += go(pos + 1, (rem + d) % K, tight && d == lim);
    if (!tight) memo[pos][rem] = res;
    return res;
}

ll countUpTo(ll x) {                       // lucky numbers in [0, x]
    if (x < 0) return 0;
    s = to_string(x);
    memset(memo, -1, sizeof memo);
    return go(0, 0, true);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll L, R;
    cin >> L >> R >> K;
    cout << countUpTo(R) - countUpTo(L - 1) << "\n";
    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static char[] s;
    static int K;
    static long[][] memo = new long[20][100];

    // ways to fill digits pos.. so the digit sum is a multiple of K
    static long go(int pos, int rem, boolean tight) {
        if (pos == s.length) return rem == 0 ? 1 : 0;
        if (!tight && memo[pos][rem] != -1) return memo[pos][rem];
        int lim = tight ? s[pos] - '0' : 9;
        long res = 0;
        for (int d = 0; d <= lim; d++)
            res += go(pos + 1, (rem + d) % K, tight && d == lim);
        if (!tight) memo[pos][rem] = res;
        return res;
    }

    static long countUpTo(long x) {      // lucky numbers in [0, x]
        if (x < 0) return 0;
        s = Long.toString(x).toCharArray();
        for (long[] row : memo) Arrays.fill(row, -1);
        return go(0, 0, true);
    }

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(new BufferedReader(new InputStreamReader(System.in)).readLine());
        long L = Long.parseLong(st.nextToken()), R = Long.parseLong(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        System.out.println(countUpTo(R) - countUpTo(L - 1));
    }
}

Python

import sys
from functools import lru_cache

def count_up_to(x, K):
    """lucky numbers in [0, x]"""
    if x < 0:
        return 0
    s = str(x)

    @lru_cache(maxsize=None)
    def go(pos, rem, tight):
        if pos == len(s):
            return 1 if rem == 0 else 0
        lim = int(s[pos]) if tight else 9
        return sum(go(pos + 1, (rem + d) % K, tight and d == lim) for d in range(lim + 1))

    return go(0, 0, True)

def main():
    L, R, K = map(int, sys.stdin.read().split())
    print(count_up_to(R, K) - count_up_to(L - 1, K))

main()

All three print 9, 142857142856594041, 1 and 75963926232 on the four test lines above.

Next episode: DP 7: DP on trees and rerooting (an answer for every root, in one pass).