Why this matters when you build with AI
Many practical questions are counting questions with a large upper limit. How many serial numbers below a limit have a certain check property? How many IDs in a range contain no repeated digit? How many codes match a rule? An AI tool asked for this often writes a loop from 1 to N. The loop is correct for N = 1000 and useless for N = 10^18, because it would need about 10^18 steps, which takes decades even at a billion steps per second.
When you ask for the fast version, the tool often writes a digit DP that looks right and is wrong. You cannot see the error by reading the code. The two errors below are common ones. Both numbers come from the programs in this lesson, run on the input N = 130, digit sum divisible by 3, at most 1 zero. The correct answer is 43.
- Lost tight flag: the program forgets the upper limit on each digit and counts every 3-digit string. It prints 330.
- Leading zeros counted: the program writes 5 as 005 and counts its zeros. It prints 36.
A brute force program (a program that tries every number and checks it) catches both in seconds. It is short enough to trust. The habit to build is simple: write the brute force first, then compare the fast version with it on every N up to a few thousand. Only then trust the fast version on big inputs.
Terms you need first
- Digits: the decimal digits of N, read from the most significant (leftmost) digit to the least. The number 130 has the digits 1, 3 and 0.
- Digit DP: a dynamic programming method (dynamic programming means you store and reuse the answer for a state that repeats) that builds the number one digit at a time. It keeps only a small summary of the digits chosen so far. That summary is the state.
- Tight prefix: the digits chosen so far are equal to the first digits of N. The next digit may not be larger than N's digit at that position. A prefix that is already smaller than N is called free, and any digits may follow it.
- Leading zero: a zero written before the first nonzero digit. The number 5 written in three positions is 005. Leading zeros are padding, so they are not digits of the number.
- Property state: the smallest summary that tells you whether the property still holds at the end. For a digit sum divisible by M, the state is the digit sum modulo M. For at most K zeros, the state is the zero count so far. Once the count passes K, the prefix is dropped.
The problem for this lesson is one I wrote for it. Count the whole numbers x from 1 up to N such that the digit sum of x is divisible by M and x has at most K zeros written inside it. Leading zeros do not count. For example, 105 has digit sum 6 (divisible by 3) and one zero, so with M = 3 and K = 1 it counts. 1005 has digit sum 6 and two zeros, so with K = 1 it does not count.
The idea, built up from a small example
Take N = 130. Write it in three digit slots: 1, 3, 0. Every number from 0 to 130 fits in three slots if we allow leading zeros, so 7 is 007 and 99 is 099. The question becomes: how many three-slot strings give a number that is at most 130?
Count them by the first digit, the way the tight flag does it by hand.
- First digit 0. The prefix is 0, which is below 1, so it is free. The last two digits can be anything from 00 to 99. That is 100 strings.
- First digit 1. The prefix is tight, equal to N's first digit. The second digit can be 0, 1, 2 (below N's 3) or 3 (equal, so still tight).
- Second digit 0, 1 or 2. The prefix is free, so the third digit can be anything. That is 3 times 10, which is 30 strings.
- Second digit 3. The prefix is still tight. The third digit must not be larger than N's last digit, 0. Only the string 130 is left, which is 1 string.
The total is 100 + 30 + 1 = 131. That is correct, because the numbers 0 to 130 are 131 numbers. Without the tight flag, the program would treat the first digit 1 as free, and it would count all 100 strings from 100 to 199, although only 31 of them are at most 130. That is the lost tight flag bug from the first section.
The leading-zero flag is a second, separate question. The string 007 is the number 7, so the program must not treat its two leading zeros as zeros of the number. A started flag records whether a nonzero digit has been written yet. Until it is set, a zero does not add to the zero count.
So each state is three numbers: started (0 or 1), r (digit sum mod M) and z (zeros written after the start). A state has at most 2 times M times (K + 1) values, which is small. The program moves from one state to another for each digit 0 to 9.
Standard technique: memoised recursion and an iterative form
There are two common ways to write a digit DP. The memoised form is a recursive function that remembers results. The iterative form moves forward one position at a time with arrays. Both are below in one program. Read the Memo struct first, then count_iter.
In the recursive form, go(pos, state, tight) returns the number of ways to fill the digits from position pos to the end so that the number has the property. When tight is false, the answer depends only on pos and the state, so it is saved in memo. When tight is true, the answer depends on N's digits too, so it is not saved. The base case at the end returns 1 when the digit sum is 0 mod M. This counts the number that was built.
In the iterative form, f[started][r][z] holds how many free prefixes have each state. At each position, every free prefix can take any digit, and the one tight prefix can drop below N by taking a smaller digit. Each step creates a new array nf. At the end, the answer is the free states with r = 0 plus the tight number itself if it has the property.
Both forms count the number 0 as well, because 0 has digit sum 0 and no zeros in its representation. The programs remove it with - 1.
Here is the complete C++17 program. It was compiled with g++ -std=c++17 -O2 -Wall -Wextra and run in a scratch folder. The output is pasted below it.
// Count x in [1, N] whose digit sum is divisible by M and that contain at most K zeros.
// Zeros written before the first nonzero digit are leading zeros and do not count.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// Digit state: started = 1 once a nonzero digit has been written,
// r = digit sum mod M, z = zeros written after the first nonzero digit.
struct State {
int started, r, z;
};
// Apply one digit d. Returns false if the zero limit K is broken.
bool step(State s, int d, int M, int K, State &out) {
out = s;
if (d == 0) {
if (s.started) {
out.z = s.z + 1;
if (out.z > K) return false;
}
return true;
}
out.started = 1;
out.r = (s.r + d) % M;
return true;
}
// Memoised form: go(pos, state, tight) counts ways to fill digits pos..end.
struct Memo {
int M, K;
vector<int> d; // digits of N, most significant first
vector<ll> memo;
vector<char> seen;
int idx(int pos, const State &s) const {
return ((pos * 2 + s.started) * M + s.r) * (K + 1) + s.z;
}
ll go(int pos, State s, bool tight) {
if (pos == (int)d.size()) return s.r == 0 ? 1 : 0;
int id = idx(pos, s);
if (!tight && seen[id]) return memo[id];
int limit = tight ? d[pos] : 9;
ll total = 0;
for (int c = 0; c <= limit; c++) {
State nxt;
if (!step(s, c, M, K, nxt)) continue;
total += go(pos + 1, nxt, tight && c == limit);
}
if (!tight) {
seen[id] = 1;
memo[id] = total;
}
return total;
}
};
// Counts x in [0, N] with the property, then removes x = 0.
ll count_memo(ll N, int M, int K) {
Memo m;
m.M = M;
m.K = K;
for (char ch : to_string(N)) m.d.push_back(ch - '0');
int L = m.d.size();
m.memo.assign((L + 1) * 2 * M * (K + 1), 0);
m.seen.assign((L + 1) * 2 * M * (K + 1), 0);
return m.go(0, State{0, 0, 0}, true) - 1;
}
// Iterative form: f[started][r][z] counts prefixes already below N's prefix.
ll count_iter(ll N, int M, int K) {
string s = to_string(N);
int L = s.size();
int Z = K + 1;
auto at = [&](int st, int r, int z) { return (st * M + r) * Z + z; };
vector<ll> f(2 * M * Z, 0), nf;
State tight{0, 0, 0};
bool alive = true;
for (int i = 0; i < L; i++) {
int di = s[i] - '0';
nf.assign(2 * M * Z, 0);
// Prefixes already below N take any digit.
for (int st = 0; st < 2; st++)
for (int r = 0; r < M; r++)
for (int z = 0; z <= K; z++) {
ll v = f[at(st, r, z)];
if (!v) continue;
for (int c = 0; c <= 9; c++) {
State nx;
if (step(State{st, r, z}, c, M, K, nx)) nf[at(nx.started, nx.r, nx.z)] += v;
}
}
// The tight prefix (equal to N so far) drops below N with a smaller digit.
if (alive) {
for (int c = 0; c < di; c++) {
State nx;
if (step(tight, c, M, K, nx)) nf[at(nx.started, nx.r, nx.z)] += 1;
}
State nx;
alive = step(tight, di, M, K, nx);
tight = nx;
}
f.swap(nf);
}
ll total = 0;
for (int st = 0; st < 2; st++)
for (int z = 0; z <= K; z++) total += f[at(st, 0, z)];
if (alive && tight.r == 0) total += 1; // N itself
return total - 1; // remove x = 0
}
// Brute force for testing: try every x.
ll brute(ll N, int M, int K) {
ll cnt = 0;
for (ll x = 1; x <= N; x++) {
string t = to_string(x);
int sum = 0, zeros = 0;
for (char ch : t) {
sum += ch - '0';
if (ch == '0') zeros++;
}
if (sum % M == 0 && zeros <= K) cnt++;
}
return cnt;
}
int main() {
ll N = 130;
int M = 3, K = 1;
cout << "N=" << N << " M=" << M << " K=" << K << "\n";
cout << "memo " << count_memo(N, M, K) << "\n";
cout << "iter " << count_iter(N, M, K) << "\n";
cout << "brute " << brute(N, M, K) << "\n";
ll big = 1000000000000000000LL;
cout << "N=10^18 M=7 K=2\n";
cout << "memo " << count_memo(big, 7, 2) << "\n";
cout << "iter " << count_iter(big, 7, 2) << "\n";
return 0;
}Real output of that program:
N=130 M=3 K=1
memo 43
iter 43
brute 43
N=10^18 M=7 K=2
memo 109262528875145021
iter 109262528875145021The brute force has no way to reach N = 10^18, so that last pair is checked only by agreement between the two forms. The program was also tested against brute force on every N from 0 to 3000 for every M from 1 to 9 and every K from 0 to 3, plus 400 random N up to 2 million. All 108,436 checks agreed. That is strong evidence for the small inputs. It is not a proof for 10^18.
The same method in Python is fast enough for this problem size. The program below takes no input, so the site can run it. It uses a memo through lru_cache, and it checks itself against brute force for every N up to 799.
Real output of that program:
N=130 m=3 k=1
digit DP: 43
brute: 43
mismatches over m 1..9, k 0..3, n 0..799: 0
N=10^18 m=7 k=2: 109262528875145021Complexity
Let L be the number of digits of N. For N = 10^18, L is 19. The states at one position are started (2 values), r (M values) and z (K + 1 values). Each state tries 10 digits. The total work is about L times 2 times M times (K + 1) times 10. For M = 9 and K = 3 that is under 14,000 steps for N = 10^18. The brute force needs about N steps, which is 10^18 here.
The memo array has (L + 1) times 2 times M times (K + 1) entries. That is also tiny. Memory is not the reason to choose a different method. The reason is the number of steps.
Two facts to keep in mind. The tight path is one path, so it is not memoised. Everything else is memoised, and the memo key must hold every field that affects the answer. For this problem the key is the position, started, r and z.
Common mistakes
-
Lost tight flag. The program counts every digit string with the right length, even those above N. On N = 130, M = 3, K = 1, the buggy version printed 330 instead of 43. The fix is to pass
tight && c == limitinto the next position, and to used[pos]as the limit only while tight. -
Leading zeros counted. The program pads 5 to 005 and counts two zeros. On the same input it printed 36 instead of 43. The fix is the
startedflag: a zero before the first nonzero digit changes nothing. -
Off-by-one on a range. A question about the range 105 to 500 asks for f(500) minus f(104), where f(n) counts 1 to n. Subtracting f(105) drops the number 105 itself. With M = 3 and K = 1, f(500) minus f(104) is 131 and f(500) minus f(105) is 130. Count up to the number just below the lower limit.
-
Overflow in the answer. The answer for N = 10^18 is 109262528875145021. A 32-bit
intholds at most 2147483647, so it cannot store this. Uselong long, as the program does. -
Forgetting the zero from x = 0. Both forms count 0 first, then remove it with
- 1. Without the- 1, the answer for N = 130 is 44.
Hands-on exercise
Change the property so that the limited digit is 7 instead of 0. The count is now: numbers from 1 to N with digit sum divisible by M and at most K sevens. Leading zeros are no longer a problem, because a leading zero is not a 7. You can remove started from the state.
Write the recursive version. Then test it against brute force on every N from 0 to 3000, for M from 1 to 9 and K from 0 to 3. A correct version agrees with brute force on every check. If one check fails, print N, M and K for the first failure and compare the two by hand on that input.
Try the exercise first.
Show the answer
The change is to the step rule. A digit 7 adds one to the zero count, and every other digit adds its value to the sum. The memo key drops started.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll count_sevens(ll N, int M, int K) {
string s = to_string(N);
int L = s.size();
vector<vector<vector<ll>>> memo(L + 1, vector<vector<ll>>(M, vector<ll>(K + 1, -1)));
function<ll(int, int, int, bool)> go = [&](int pos, int r, int z, bool tight) -> ll {
if (pos == L) return r == 0 ? 1 : 0;
if (!tight && memo[pos][r][z] >= 0) return memo[pos][r][z];
int limit = tight ? s[pos] - '0' : 9;
ll total = 0;
for (int c = 0; c <= limit; c++) {
int nz = z + (c == 7);
if (nz > K) continue;
total += go(pos + 1, (r + c) % M, nz, tight && c == limit);
}
if (!tight) memo[pos][r][z] = total;
return total;
};
return go(0, 0, 0, true) - 1; // minus x = 0
}I compiled this with g++ -std=c++17 -O2 and tested it against brute force on every N from 0 to 3000, for M from 1 to 9 and K from 0 to 3. All 108,036 checks agreed. For N = 130, M = 3 and K = 1 it prints 43, the same as brute force.
Practice problems
Each problem has its own answer. The answers come from brute force programs I ran, so check your DP against them.
- Count the numbers x from 1 to 98765 whose digits are all different. For example, 1023 counts and 1123 does not. Hint: the state needs the set of digits used so far. A set of 10 digits fits in a 10-bit mask. A
startedflag is still needed.
Show the answer
-
A digit DP with a 10-bit mask of used digits and a
startedflag gives this count. The brute force loop over 1 to 98765 prints 32490. -
Count the numbers x from 100 to 500 whose digit sum is divisible by 3 and that have at most 1 zero. Use M = 3 and K = 1. Hint: compute f(500) minus f(99), where f(n) counts the numbers from 1 to n with the property.
Show the answer
-
The range count is f(500) minus f(99). A brute force loop over 100 to 500 also prints 132. Here f(99) is the count for 1 to 99, which is the part of the range below 100.
-
Count the numbers x from 1 to 1000 whose digits never go down from left to right. For example, 1123 and 555 count, and 1213 does not. Hint: the property state is the last digit written, not a sum. Only a digit that is at least the last digit may follow it. Think about what the leading zeros do to the first real digit.
Show the answer
-
The state is the last digit, a value from 0 to 9, plus the
startedflag. A new nonzero digit must be at least the last digit. A brute force loop over 1 to 1000 gives 219. -
Count the numbers x from 1 to 999 that contain no digit 0 and whose digit sum leaves remainder 1 when divided by 4. Hint: this is the zero limit set to K = 0 with a different modulus. You do not need the zero count in the state, but you do need the sum modulo 4.
Show the answer
- The state is the digit sum modulo 4. Any digit 0 is rejected at once. A brute force loop over 1 to 999 gives 205.
Checklist
- Write the brute force first. Run it on small N and keep it.
- Compare the fast version with brute force on every N from 0 to a few thousand, for every parameter you use.
- Check the output on N = 0, N = 9 and N = 10. Each case catches a different off-by-one.
- Name the four parts of the state: tight, leading-zero flag, property state and position. Say which of them the memo key holds.
- Use
long longfor the answer and for N when N can reach 10^18. - Subtract the case x = 0 once, and say why in a comment.
- Count a range [L, R] as f(R) minus f(L - 1), not f(L).
A prompt you can give to an AI tool for this kind of task:
Write a C++17 program that counts x in [1, N] for N up to 10^18, where the
digit sum of x is divisible by M and x has at most K zeros inside it
(leading zeros do not count). Use a digit DP with a tight flag, a leading-zero
flag and a state for the digit sum mod M and the zero count. Also write a brute
force function. Print both answers for N = 130, M = 3, K = 1 and state which
value the DP should print.A good answer has the state with all four parts, a base case that returns 1 when the sum is 0 modulo M, a - 1 for the zero x, and a brute force function. Check two things: that the DP prints 43 for N = 130, M = 3, K = 1, and that the answer changes when you move the leading-zero flag out of the state. If the DP prints 330 or 36, the tight flag or the leading-zero flag is missing.
Summary
A digit DP walks the digits of N from left to right and counts the numbers that have a property. The tight flag keeps track of whether the prefix still matches N. The leading-zero flag keeps padding zeros from counting. The property state is the smallest summary that answers the question at the end. Memoised recursion and the iterative form use the same states and give the same answers. Test both against brute force before you trust them on large N.