AlgoScope

Digit DP

Counting the numbers up to N with some property of their digits sounds like a loop over N numbers, but the digits can be placed one at a time from the left, and the only thing the count depends on is whether the digits placed so far still match N exactly. That is the tight flag: while tight, the next digit may not exceed N's digit. Once a smaller digit has been chosen, the rest is free and every allowed digit goes. Two states per position, filled from the last position backwards, and the answer is the tight state at the first position. Adding state, a digit sum, a remainder, a last digit, is what turns the same table into an answer for harder properties.

The player

Digit DP counting numbers up to 275 without the digit 7.pos 0pos 1pos 2endtightfree11

How many numbers from 0 to 275 never contain the digit 7? Checking each number is O(n). Instead, place digits from the left. Each column holds, for each state, the number of ways to fill that position and everything after it: "tight" means the digits so far match 275 exactly, so the next digit may not go above the digit 275 has there. "free" means a smaller digit was already chosen and anything allowed goes. Fill from the right, where an empty suffix counts as one number.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 3, with their answers.

  1. Position 2 is tight and 275's digit here is 5. How many ways complete the number?

    • 5
    • 6
    • 9

    Answer: 6. Digits below 5 go free: 5 x 1. The digit 5 itself stays tight, adding 1.

  2. Position 1 is tight and 275's digit here is 7. How many ways complete the number?

    • 63
    • 72
    • 81

    Answer: 63. Digits below 7 go free: 7 x 9. The digit 7 itself stays tight, but it is forbidden, so it adds 0.

  3. Position 0 is tight and 275's digit here is 2. How many ways complete the number?

    • 162
    • 225
    • 243
    • 729

    Answer: 225. Digits below 2 go free: 2 x 81. The digit 2 itself stays tight, adding 63.

How it runs, step by step

  1. How many numbers from 0 to 275 never contain the digit 7? Checking each number is O(n). Instead, place digits from the left. Each column holds, for each state, the number of ways to fill that position and everything after it: "tight" means the digits so far match 275 exactly, so the next digit may not go above the digit 275 has there. "free" means a smaller digit was already chosen and anything allowed goes. Fill from the right, where an empty suffix counts as one number.

    Digit DP counting numbers up to 275 without the digit 7.

  2. Position 2, free: any of the 9 allowed digits can go here, and the rest is still free, so 9 x 1 = 9.

    Free at position 2: 9.

  3. Position 2, tight: 275 has the digit 5 here. A digit below 5 frees the rest: 5 allowed choices x 1 = 5. Choosing 5 itself keeps the number tight, adding the tight count of the next position, 1. Total 6.

    Tight at position 2: 6.

  4. Position 1, free: any of the 9 allowed digits can go here, and the rest is still free, so 9 x 9 = 81.

    Free at position 1: 81.

  5. Position 1, tight: 275 has the digit 7 here. A digit below 7 frees the rest: 7 allowed choices x 9 = 63. Choosing 7 itself keeps the number tight, but 7 is the forbidden digit, so that branch adds nothing. Total 63.

    Tight at position 1: 63.

  6. Position 0, free: any of the 9 allowed digits can go here, and the rest is still free, so 9 x 81 = 729.

    Free at position 0: 729.

  7. Position 0, tight: 275 has the digit 2 here. A digit below 2 frees the rest: 2 allowed choices x 81 = 162. Choosing 2 itself keeps the number tight, adding the tight count of the next position, 63. Total 225.

    Tight at position 0: 225.

  8. 225 numbers from 0 to 275 never use the digit 7, read from the tight cell at position 0. The table has 2 x 3 cells for a 3-digit limit, so the count is O(digits) however large 275 is. A limit with twenty digits costs forty cells, not a scan of a twenty-digit number. Shorter numbers ride along as leading zeros, which is why forbidding 0 itself would need a third flag for "has the number started". The pattern generalises by adding state: a running digit sum, a remainder, or whether a digit has repeated, each multiplying the rows.

    225 numbers without the digit 7.

The code

Digit DP, in Python

def count_without(n, bad):                                    # numbers in 0..n that never use digit bad
    digits = [int(c) for c in str(n)]
    memo = {}
    def ways(pos, tight):                                     # ways to finish from position pos
        if pos == len(digits):                                # every digit placed: one number
            return 1
        if (pos, tight) not in memo:
            limit = digits[pos] if tight else 9               # tight: may not exceed n's digit
            total = 0
            for d in range(limit + 1):
                if d == bad:
                    continue
                total += ways(pos + 1, tight and d == limit)  # equal to n's digit: still tight
            memo[(pos, tight)] = total
        return memo[(pos, tight)]
    return ways(0, True)

Digit DP, in JavaScript

function countWithout(n, bad) {                                  // numbers in 0..n that never use digit bad
  const digits = [...String(n)].map(Number);
  const memo = new Map();
  function ways(pos, tight) {                                    // ways to finish from position pos
    if (pos === digits.length) return 1;                         // every digit placed: one number
    const key = `${pos},${tight}`;
    if (!memo.has(key)) {
      const limit = tight ? digits[pos] : 9;                     // tight: may not exceed n's digit
      let total = 0;
      for (let d = 0; d <= limit; d++) {
        if (d === bad) continue;
        total += ways(pos + 1, tight && d === limit);            // equal to n's digit: still tight
      }
      memo.set(key, total);
    }
    return memo.get(key);
  }
  return ways(0, true);
}

Digit DP, in Kotlin

fun countWithout(n: Int, bad: Int): Int {                      // numbers in 0..n that never use digit bad
    val digits = n.toString().map { it - '0' }
    val memo = HashMap<Pair<Int, Boolean>, Int>()
    fun ways(pos: Int, tight: Boolean): Int {                    // ways to finish from position pos
        if (pos == digits.size) return 1                         // every digit placed: one number
        return memo.getOrPut(pos to tight) {
            val limit = if (tight) digits[pos] else 9            // tight: may not exceed n's digit
            (0..limit).filter { it != bad }.sumOf { d ->
                ways(pos + 1, tight && d == limit)               // equal to n's digit: still tight
            }
        }
    }
    return ways(0, true)
}

Write it yourself

Define countWithoutDigit(n, digit) and return how many numbers from 0 to n do not contain the digit. 0 counts. It runs in your browser against this lesson's own 3 examples.

// Walk the digits of n from the left, counting what is free below each prefix rather than testing every number. The count starts at 0, which contains no digit at all.function countWithoutDigit(n, digit) { return 0;}
6 linesTab indents. Escape, then Tab, leaves the editor. Ctrl-Enter runs (Cmd-Enter on a Mac).

    Remember

    • Place digits from the left. The tight flag says whether the prefix still equals N's prefix.
    • Tight: digits below N's digit go free, N's digit itself stays tight. Free: every allowed digit goes.
    • Fill from the right, one column per position. Harder properties add rows of state, never more columns.

    Where this is used

    Splitting an address range into CIDR blocksNetworking

    Security groups and route tables take prefixes like 10.0.0.0/22, not arbitrary endpoints, so covering 10.0.0.5 through 10.0.3.200 means splitting it into whole blocks first, which is what Python's ipaddress.summarize_address_range does. It walks the bits of each bound from the left the way this walks digits: while the prefix still equals the bound nothing can be emitted, and the first bit where it drops below leaves every later bit free, which is exactly one prefix. That is why a range over W-bit addresses never needs more than 2W - 2 prefixes, one per bit position along each of the two boundary paths.

    Rank queries in a wavelet treeText indexing

    Libraries that build an FM-index on a wavelet tree, such as sdsl-lite's csa_wt or NVBIO's protein search, have to answer how many values in a block are smaller than x while the data stays compressed. The tree answers it one bit of x per level: where x has a 1, everything holding a 0 at that position is already smaller whatever its lower bits are, so the whole side is added in a single step, while the walk carries on down x's own bit path. That bit path is the tight state and the side added wholesale is the free one, so the count falls out of a single root-to-leaf walk instead of a scan.

    Covering a map region with index cellsGeospatial

    A 2dsphere index in MongoDB, like Google Maps and Foursquare before it, sits on the S2 library, which answers a region query by covering the region with cells off a quadtree over the sphere. The coverer starts at the six cube faces and keeps splitting: a cell the region fully contains is terminal and goes in whole, and only a cell straddling the edge is subdivided again. Contained is the free state and straddling is the tight one, so the work is bounded by the boundary path rather than by the area, and a cell budget caps how far that path is followed.

    Rank and count in Redis sorted setsDatabases

    ZRANK and ZCOUNT report how many members sit below a score without touching them, because every forward pointer in the skiplist carries a span, the number of members it skips over. The walk starts at the top level and adds the span of each jump that stays below the target, dropping a level only when the next jump would overshoot, so whole runs are counted in one step and only the boundary path is descended. Those stored spans play the part the memo table plays here: the free side is a number you already have rather than a subtree you still have to visit.

    Why it works this way

    Why place digits from the left and not the right?

    Whether a number is at most N is decided at the first position where the two differ, and nothing after that position can change the verdict. Working left to right is what lets that comparison collapse into a single bit of state, still equal or already below, and once it is already below the bound is finished with. From the right you would have to carry every digit placed so far to know what is still allowed, which is the same as not summarising at all.

    Once free, never tight again

    The recursive call passes tight && d == limit, and dropping the tight && is the bug that catches nearly everyone the first time. In the free state limit is 9, so without that guard a prefix that had already gone below N snaps back to tight the moment a 9 is chosen, clamping the rest of the number to N's digits and losing a large part of the count. The flag is deliberately one-way: dropping below the bound at any position frees every position after it for good.

    Leading zeros are not the same as the digit zero

    Every number is placed as a fixed-width string, so 7 under a bound of 275 is built as 007 and those padding zeros look like real digits to the recursion. For never uses a 7 that does no harm, but for anything that reads the digits themselves, no zero anywhere, strictly increasing digits, how many distinct digits, the invented zeros give a wrong answer. The fix is a second flag, usually called started, false while only zeros have been placed and true from the first nonzero digit, so the positions before it are skipped rather than counted as zeros.

    Every piece of state has to be in the memo key

    There is only one tight prefix at each position, N's own, so (pos, true) is computed once and never read back again. All of the reuse lives in (pos, false), where every prefix that has already dropped below N arrives. That is also where the quiet wrong answer comes from once you add state: put a running digit sum or a remainder mod m into the recursion and leave it out of the key, and two prefixes with different sums share one cached number. The key has to hold exactly what the rest of the count depends on, no less, and no more or it stops hitting.

    Read more

    Next up