cf.completefrontend
DYNAMIC PROGRAMMING · ADVANCED

Digit DP

Count the numbers up to a limit that follow a digit rule by choosing their digits one at a time, from left to right.

Time O(D × S × 10)Space O(D × S)5 practice problemsStep-through picture

The idea

Digit DP answers questions like "how many numbers from 0 to 1,000,000,000 have digits that add up to 10?" Checking each number one by one would take a billion steps. Instead, you build the numbers digit by digit and count them in groups.

The state is: which digit position you are filling (pos), what you need to remember about the digits so far (here their sum), and whether every digit so far equals the limit's digit (tight). While tight is true, the next digit can't go above the limit's digit at that position; once you pick a smaller digit, every later digit is free from 0 to 9.

Many different numbers reach the same state, such as "position 3, sum so far 7, not tight". Each state is counted once and memoized, so the work depends on the number of digits, not the size of the limit.

An everyday example

A combination lock with a top setting

Picture a number lock with dials, where you may only set combinations up to a given top setting, such as 2-5-3. You set the dials left to right. If the first dial is below 2, every later dial can be anything. If it is exactly 2, the next dial must stay at or below 5, and so on. Counting the allowed settings that satisfy a rule only needs to know which dial you're on, what the rule needs so far, and whether you are still matching the top setting.

How the example maps to the code
In the exampleIn the code
The top settinglimit, split into digits
Which dial you are settingpos
Still matching the top setting so fartight
The highest value this dial may takemaxDigit
What the rule needs to knowsum of the digits so far

From the slow way to digit dp

  1. Start with brute force: go through every number from 0 to limit, add up its digits, and count the ones that hit target. For a limit of 1,000,000,000 that is a billion numbers, each with up to 10 digits to add. For a limit of 10^18, it would never finish.
  2. Build the numbers instead of listing them. Write every number with the same count of digits as the limit, using zeros in front, so 25 becomes 025 when the limit has three digits. Then a number is a choice of one digit per position, from left to right. Leading zeros add nothing to a digit sum, so they cause no trouble here.
  3. Notice what matters after choosing the first few digits: the position you're at, the sum so far, and one yes-or-no fact called tight. tight is true while every digit so far equals the limit's digit, and then the next digit can't go above the limit's digit. Once any digit is smaller, the number is already below the limit, and every later digit is free from 0 to 9.
  4. Many prefixes share the same (pos, sum, tight): 04 and 13 both reach position 2 with sum 4, not tight. They have exactly the same ways to finish. So write count(pos, sum, tight), try each allowed digit, and memoize it. That memoized count is digit DP.

How it works

  1. Turn the limit into an array of digits, most significant first.
  2. Write count(pos, sum, tight): how many ways to fill positions pos and later so the full number's digit sum is target.
  3. If pos reaches the end, return 1 if sum === target, else 0. If sum already passed target, return 0 early.
  4. The largest digit allowed here is maxDigit = tight ? digits[pos] : 9.
  5. Try each digit d from 0 to maxDigit, and add count(pos + 1, sum + d, tight && d === maxDigit).
  6. Memoize on pos, sum, and tight, and start with count(0, 0, true).

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function countDigitSum(limit, target) {
  2. const digits = String(limit).split("").map(Number);
  3. const memo = new Map();
  4. function count(pos, sum, tight) {
  5. if (sum > target) return 0;
  6. if (pos === digits.length) return sum === target ? 1 : 0;
  7. const key = pos + "," + sum + "," + tight;
  8. if (memo.has(key)) return memo.get(key);
  9. const maxDigit = tight ? digits[pos] : 9;
  10. let total = 0;
  11. for (let d = 0; d <= maxDigit; d++) {
  12. total += count(pos + 1, sum + d, tight && d === maxDigit);
  13. }
  14. memo.set(key, total);
  15. return total;
  16. }
  17. return count(0, 0, true);
  18. }

How fast it is

TimeO(D × S × 10)
Extra memoryO(D × S)

D digit positions times S possible sums times 2 values of tight are the states, and each tries up to 10 digits. The memo has one entry per state.

  • Best caseO(D × 10)

    target = 0: only states with sum 0 survive, so about 2 × D states each try 10 digits, most returning 0 at once.

  • Average caseO(D × S × 10)

    A typical target: up to D positions, S = target + 1 sums, and 2 values of tight, each trying 10 digits. For a limit of 1,000,000,000 and target 10, that is 98 states and 892 calls.

  • Worst caseO(D × S × 10)

    A large target, up to 9 × D: no sum goes over it early, so every sum from 0 to the target can appear at every position.

Common mistakes

  • Forgetting that the result counts from 0, so a range [low, high] needs count(high) - count(low - 1).
  • Keeping tight true after picking a smaller digit. Once a digit is below the limit's digit, every later digit is free.
  • Mixing leading zeros with real zeros in rules about which digits appear. Add a started flag when it matters.
  • Passing a number above 2^53 as a JavaScript number, which loses digits. Pass it as a string or BigInt for very large limits.

When to use it

Look for these clues in a problem:

  • The question counts numbers in a range, often up to 10^9 or 10^18, that follow a rule about their digits.
  • The rule looks at digits: their sum, whether they repeat, which digits appear, whether neighbors differ.
  • The range is [low, high], which you can answer as count(high) - count(low - 1).
  • Checking every number in the range would be far too slow.

Check yourself

Answer each one in your head first, then open it.

Why is tight part of the memo key?

A tight state can only use digits up to the limit's digit, while a free state can use 0 to 9. They have different numbers of ways to finish, so they must be stored apart.

In the trace, why could count(2, 1, false) be reused for 103 when it was first computed for 013?

Both prefixes reach position 2 with sum 1 and are already below the limit. The last digit has the same choices for both, so the count is the same.

Why is the early return sum > target safe?

Digits are never negative, so the sum only grows. Once it is over the target, no way of finishing can bring it back.

About how many states are there for a limit with 19 digits and target 30?

At most 19 × 31 × 2 = 1,178, since pos has 19 values, sum 31 values that matter, and tight 2. Each tries up to 10 digits.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Every number from 0 to limit, written with leading zeros, matches exactly one path of digit choices that never goes above the limit. The tight rule makes sure of that: while the prefix equals the limit's prefix, the next digit is capped at the limit's digit, and once a digit is smaller, the number is below the limit whatever comes next. So counting paths that end with sum target counts exactly the right numbers, each once.

The memo is safe because count(pos, sum, tight) depends only on those three values. Two prefixes with the same position, the same digit sum, and the same tight have exactly the same set of ways to finish, so they get the same count. The early return when sum > target is safe too, because digits are never negative, so the sum can't come back down.

It always ends, because every call moves pos one step to the right, and pos === digits.length is a base case. Each state is computed once and tries at most 10 digits, so the work depends on the number of digits and the target, not on the size of the limit.

Going deeper

3 more ideas

What one state means

count(pos, sum, tight) is the number of ways to choose digits for positions pos to the end so the whole number stays at most the limit and its digits add up to target, given that the digits already chosen add up to sum. tight says whether those chosen digits are exactly the limit's first digits.

Why leading zeros are fine here

Numbers shorter than the limit are written with zeros in front, so 25 with a 3-digit limit is 025. Zeros don't change a digit sum, so they cause no trouble here. For rules like "no repeated digits", you need one more flag, started, so leading zeros are not counted as real digits.

How much work it does

There are D positions, up to S possible sums, and 2 values of tight, and each state tries 10 digits. That is O(D * S * 10). For a limit of 10^18, D = 19 and S is at most 171, so a few tens of thousands of steps.

Work it by hand

Every step in a table, with why

Count the numbers from 0 to 132 whose digits add up to 4. Each row is one call starting, finishing, or answered from the memo.

limit = 132, target = 4, so digits = [1, 3, 2]

StepCallmaxDigitResultWhat happensWhy
1count(0, 0, true)1waitsFirst digit: 0 or 1tight is true, so the first digit can't go above the limit's first digit, 1.
2count(1, 0, false)9waitsFirst digit was 00 is below 1, so tight becomes false and the next digits are free.
3count(2, 0, false)91Only 004 worksLast position: only the digit 4 brings the sum to 4. Digits 5 to 9 overshoot and return 0 on line 5.
4count(2, 1, false)91Only 013 worksSum so far is 1, so the last digit must be 3.
5count(2, 2, false)91Only 022 worksEach of these is saved in the memo.
6count(2, 3, false)91Only 031 worksSaved under key "2,3,false".
7count(2, 4, false)91Only 040 worksThe sum is already 4, so only a final 0 keeps it there.
8count(1, 0, false)95SavedSecond digits 0 to 4 each gave 1; digits 5 to 9 made the sum go over 4 and returned 0 at once.
9count(0, 0, true)1waitsNow try first digit 11 equals the limit's first digit, so the call is count(1, 1, true): still tight.
10count(1, 1, true)3waitsSecond digit: 0 to 3Tight, so the second digit can't go above 3.
11count(2, 1, false)-1Memo hit: 103Second digit 0 makes it free, with sum 1. That state was solved for 013, so line 8 returns the saved 1.
12count(2, 2, false)-1Memo hit: 112Same state as for 022.
13count(2, 3, false)-1Memo hit: 121Same state as for 031.
14count(2, 4, true)21Still tight: 130Second digit 3 equals the limit's, so tight stays true, and the last digit can only be 0 to 2. Only 0 works.
15count(1, 1, true)34SavedThree memo hits plus one new tight state.
16count(0, 0, true)19Done5 + 4 = 9. Line 17 returns it.

It returns 9: 4, 13, 22, 31, 40, 103, 112, 121, and 130. The memo ends with 9 states, and the whole run makes 70 calls, most of them quick returns for sums over 4.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Digit DPO(D × S × 10)O(D × S)Limits too big to scan, such as 10^18, with a rule that only needs a little memory about the digits so far.
Check every numberO(n log n)O(1)Limits up to about a few million, or to check the digit DP on small limits.
Counting formulaO(D × S)O(S)Only for simple rules over a full range like 0 to 10^D - 1, where a stars-and-bars count with inclusion and exclusion gives digit sums directly. A ragged limit like 132 makes it hard to get right.

Extra memory: O(D × S) for the memo, plus O(D) for the call stack, which is never deeper than the number of digits plus one.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Digit DP and the other approaches, on a scale where each line up is 10 times more steps.
  • Digit DP O(D × S × 10)
  • Check every number O(n log n)
  • Counting formula O(D × S)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Digit DP1,00010 million10 trillion
Check every number339,96620 million
Counting formula1001 million1 trillion

Inputs that need care

5 tricky inputs
limit = 0, target = 0
digits is [0], the only path is 0, and it returns 1: the number 0 has digit sum 0.
A target no number can reach: limit = 132, target = 40
It returns 0, but only after 120 calls. A check like target > 9 * digits.length can return 0 at once.
A range [low, high] instead of [0, limit]
Count up to high and subtract the count up to low - 1. When low is 0, skip the subtraction, since String(-1) would give the digit list [NaN, 1].
A limit above 2^53, such as 10^18
As a JavaScript number it loses its last digits before the code even sees it. Pass the limit as a string or a BigInt and split that into digits.
A rule that cares about leading zeros, like "no repeated digits"
007 would look like it repeats 0. Add a started flag to the state so zeros before the first real digit aren't counted.

Variations and follow-ups

Twists interviewers add

Divisible by k

Replace sum with rem, the remainder of the number so far divided by k. Each digit d changes it to (rem * 10 + d) % k. At the end, count it if rem === 0.

Digits that never go down

Keep the previous digit in the state, and only allow digits that are at least as big. The state becomes (pos, prev, tight), with up to 10 values for prev.

Banned digits

To count numbers without a 4, skip d === 4 in the loop. When tight is true and the limit's own digit is 4, the tight path simply ends there, since that digit can't be used.

Bottom-up form

The same counts can be filled in a table from the last position to the first, with tight handled by walking along the limit's digits once. It avoids recursion, though the memoized version is usually easier to get right.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "how many numbers from low to high" with a rule about digits, and a high as large as 10^9 or 10^18. A limit that big rules out a scan.
  • Name the state out loud: position, the small fact the rule needs (here the sum), and tight. Then explain tight with an example: under a limit of 132, after picking 1 the next digit can be at most 3.
  • Test a small limit against brute force: write the slow loop too, and compare for every limit up to 1,000. That catches almost every tight bug.
  • Expect "now count over a range". Answer with count(high) - count(low - 1), and handle low = 0 and big numbers as strings.

Where frontend code uses it

The same idea in real UI code
  • Counting how many ticket, invoice, or order numbers in a range pass a digit rule, without listing them, fits digit DP.
  • Pagination and numbering features that skip numbers with certain digits (some buildings skip floors with a 4) can count the valid numbers below a limit this way.

Related algorithms