LESSON 323 OF 348 · DYNAMIC PROGRAMMING

Numbers With Digit Product P in TypeScript: Digit Dynamic Programming

Practice O(n * p * digits) Read the full explanation

Given two non-negative integers N and P, return the number of base-10 numbers with N digits and with the digit product equal to P

Example:

Input: N = 3, P = 6
Output: 9
Explanation: [
    123,
    132,
    213,
    231,
    312,
    321,
    116,
    161,
    611
]

Notes:
N <= 12

STEP 1 OF 10

Guided

Ctrl + Enter to check

TYPESCRIPT · DYNAMIC PROGRAMMING

Digit Product Numbers in TypeScript, explained

Problem overview

The method countNumbers(n, p) counts the base-10 numbers with exactly n digits whose digits multiply to p. A number can't start with 0, so a 3-digit number runs from 100 to 999.

For n = 3 and p = 6 the answer is 9. The digits 1, 2, 3 in any order give six numbers (123, 132, 213, 231, 312, 321), and the digits 1, 1, 6 in any order give three more (116, 161, 611). The notes allow n up to 12.

Approach: track the product so far

Trying every n-digit number means up to 9 * 10^11 candidates for n = 12, far too slow. Instead, count by building numbers one digit at a time and remembering only the product so far.

Let dp[i][j] be the number of i-digit numbers whose digit product is j. Appending a digit d to such a number gives an (i + 1)-digit number with product j * d, so dp[i][j] flows into dp[i + 1][j * d].

The product can grow huge (nine 9s multiply to 387,420,489), but we only care about products up to p. A product that has gone above p can never come back down to p, with one exception: appending a 0 makes any product 0. That exception matters only when p is 0. So instead of dropping oversized products, the table has one extra column, p + 1, that means "larger than p". The columns are 0 to p plus that bucket, so each row has p + 2 cells.

The bucket behaves correctly when extended: a product above p times a digit from 1 to 9 stays above p, and times 0 it becomes 0. Taking Math.min(j * d, p + 1) gives exactly this, because (p + 1) * d is at least p + 1 for d from 1 to 9.

A small case, n = 2 and p = 6. Row 1 has columns 0 to 7. The digits 1 to 6 land in columns 1 to 6, and the digits 7, 8 and 9 all land in column 7:

length 1: [0, 1, 1, 1, 1, 1, 1, 3]

Row 2, column 6 collects the ways to reach product 6: from product 1 with digit 6, from 2 with 3, from 3 with 2, and from 6 with 1. That is 1 + 1 + 1 + 1 = 4, the numbers 16, 23, 32 and 61.

Step by step

Handle n = 0. A number has at least one digit, so return 0. The code below writes into row 1, which exists only when n is at least 1.
Create the table. Make n + 1 rows, each a separate array of p + 2 zeros.
Fill row 1. A 1-digit number is a single digit from 1 to 9 (0 is not allowed as a leading digit).
Place each digit. Add 1 to dp[1][Math.min(i, p + 1)]. Use +=, because for a small p several digits land in the bucket column.
Loop over lengths i from 1 to n - 1. Each pass reads row i, which is complete, and writes row i + 1.
Loop over products j from 0 to p + 1, including the 0 column and the bucket.
Try every digit d from 0 to 9. Zero is fine here, since only the first digit has to be nonzero.
Find the new column with Math.min(j * d, p + 1).
Add the counts from dp[i][j] into dp[i + 1][col]. Empty cells hold 0, so no check is needed.
Return dp[n][p]. For n = 1 the loops don't run and row 1 already holds the answer.

The solution in TypeScript

class Solution {

    countNumbers(n: number, p: number): number {
        if (n === 0) {
            return 0;
        }
        let dp: number[][] = new Array(n + 1);
        for (let i = 0; i <= n; i++) {
            dp[i] = new Array(p + 2).fill(0);
        }
        for (let i = 1; i < 10; i++) {
            dp[1][Math.min(i, p + 1)] += 1;
        }
        for (let i = 1; i < n; i++) {
            for (let j = 0; j <= p + 1; j++) {
                for (let d = 0; d < 10; ++d) {
                    const col = Math.min(j * d, p + 1);
                    dp[i + 1][col] += dp[i][j];
                }
            }
        }
        return dp[n][p];
    }
}

TypeScript details worth knowing:

new Array(n + 1) starts empty. It has n + 1 unset slots, so the first loop gives every slot its own row. Reusing one row for all slots, as in new Array(n + 1).fill(new Array(p + 2).fill(0)), would make every row the same object.
Every row needs fill(0). An unset slot is undefined, and undefined + 1 is NaN.
Counts are exact. A number is a double and holds integers exactly up to 2^53, about 9 * 10^15. The largest possible count here is below 9 * 10^11, so there is no precision loss. For n = 12 and p = 0 the function returns 617570463519, which is larger than 2^32 but still exact.
The product is capped before it is stored. j * d is at most 9 * (p + 1) before Math.min trims it, so no product ever grows out of control.

Complexity

Time: O(n * p * 10), which is O(n * p). There are n - 1 passes, each handling p + 2 product columns with 10 digits.

Space: O(n * p). The table has (n + 1) rows of p + 2 cells. Only the previous row is ever read, so two rows would do.

Edge cases and common mistakes

p = 0. Column 0 counts the numbers that contain at least one zero digit. For n = 2 the answer is 9 (10, 20, ..., 90). For n = 1 it is 0, because 0 itself isn't a 1-digit number here.
p = 1. Only numbers made entirely of 1s qualify, so n = 3 gives 1.
p bigger than any product. n = 1 and p = 10 gives 0, since no single digit equals 10.
Dropping oversized products. If products above p were thrown away, p = 0 would lose every number whose zero comes after a large product, such as 90 for p = 0.
Using = instead of += in row 1. The bucket column would end up with 1 instead of the count of large digits.
Allowing a leading zero. Starting the first loop at 0 would count 1-digit "numbers" with product 0 and inflate every longer row.

Testing

n = 3, p = 6 gives 9.
n = 2, p = 12 gives 4: 26, 34, 43 and 62.
n = 4, p = 0 gives 2439.
n = 1, p = 7 gives 1.
n = 0, p = 5 gives 0.

Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free