LESSON 347 OF 414 · DYNAMIC PROGRAMMING

Numbers With Digit Product P in Rust: 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

Digit Product Numbers in Rust, explained

Problem overview

The function count_numbers receives n and p and returns how many base-10 numbers with exactly n digits have a digit product equal to p. The digit product is what you get by multiplying all the digits together. A number cannot start with 0.

For n = 3 and p = 6 the answer is 9. The digits {1, 2, 3} give six numbers (123, 132, 213, 231, 312, 321), and the digits {1, 1, 6} give three (116, 161, 611).

Approach: count by product, one digit at a time

With n up to 12 there are up to 9 * 10^11 candidates, far too many to test one by one. The key fact is that appending a digit d to a number multiplies its product by d. So the product of a longer number depends only on the product of the shorter one and the new digit, and the shorter number's digits no longer matter.

Let dp[i][j] be the number of i-digit numbers with product j. Row 1 is simple: each digit 1 to 9 is a one-digit number with product equal to itself. Row i + 1 comes from row i by trying all ten appended digits.

There is one catch. Products can get big, and the table can only have columns up to p. Dropping a product larger than p is wrong when p is 0: the product of every number is above 0 until it meets a 0 digit, and then it becomes 0. So the table gets one extra column, p + 1, that stands for "any product larger than p". A product above p times a digit from 1 to 9 stays above p, and times 0 it becomes 0, so this single bucket tracks everything correctly.

Step by step

Handle n = 0. A number has at least one digit, so there is nothing to count. Return 0 early with the return keyword and a semicolon. The table below writes to row 1, which exists only when n is at least 1.
Convert and build the table. Shadow n and p as usize, then create n + 1 rows of p + 2 zeros: columns 0 to p plus the overflow column. The cells are i64 because the counts outgrow i32: among 12-digit numbers, more than 600 billion contain a 0 digit.
Fill row 1. Loop over the digits 1 to 9 (the range 1..10, which excludes 10), since a number can't start with 0.
Place each digit. Add 1 to dp[1][min(i, p + 1)]. The digit i has product i, unless that is above p, in which case it goes to the overflow column. Use +=: when p is small, several digits land in the same column.
Extend row by row. Loop i from 1 to n - 1. The pass for i fills row i + 1.
Loop over every column j from 0 to p + 1, including the overflow column and column 0.
Try every digit d from 0 to 9. Only the first digit has to be non-zero, and row 1 already took care of that.
Find the new column. It is min(j * d, p + 1): the old product times the digit, capped at the overflow column.
Add the counts: dp[i + 1][col] += dp[i][j]. An empty cell adds 0, so no check is needed.
Return dp[n][p] as the last expression. For n = 1 the row loop doesn't run and row 1 is already the answer.

The solution in Rust

impl Solution {
    fn count_numbers(n: i32, p: i32) -> i64 {
        if n == 0 {
            return 0;
        }
        let n = n as usize;
        let p = p as usize;
        let mut dp = vec![vec![0i64; p + 2]; n + 1];
        for i in 1..10 {
            dp[1][std::cmp::min(i, p + 1)] += 1;
        }
        for i in 1..n {
            for j in 0..=p + 1 {
                for d in 0..10usize {
                    let col = std::cmp::min(j * d, p + 1);
                    dp[i + 1][col] += dp[i][j];
                }
            }
        }
        dp[n][p]
    }
}

The Rust details worth knowing:

Early return versus tail expression. Leaving a function in the middle needs return 0;. The final line dp[n][p] has no return and no semicolon; with a semicolon it would become a statement and the function would yield ().
Integer types never mix. In the first loop, i is passed to min together with p + 1, so the compiler makes it a usize. In the inner loop d is written 0..10usize so that j * d multiplies two usize values; a plain 0..10 would be inferred from the multiplication too, but the suffix states the type.
Why i64. The result type i64 holds up to about 9.2 * 10^18. An i32 tops out near 2.1 * 10^9. In a build with optimizations, as the lessons use, overflow wraps silently, so a too-small type gives wrong answers with no error.
The range 0..=p + 1. The operator + binds tighter than ..=, so this means 0..=(p + 1).
Cloned rows. vec![vec![0i64; p + 2]; n + 1] makes n + 1 independent rows, so writing to row i + 1 doesn't change row i.

Complexity

Time: O(n * p * 10), that is O(n * p). For each of the n - 1 row transitions there are p + 2 columns and 10 digits.

Space: O(n * p). The table has (n + 1) * (p + 2) cells. A very large p would need a very large table, so the method suits moderate values of p.

Edge cases and common mistakes

Zero digits. n = 0 returns 0 through the early return.
Product 0. n = 2, p = 0 gives 9: the numbers 10, 20, ..., 90. The overflow column is what makes this work, since every starting digit begins above 0.
One digit. n = 1, p = 5 gives 1. The lesson's table counts only the digits 1 to 9 for one-digit numbers, so n = 1, p = 0 gives 0.
Impossible products. n = 2, p = 100 gives 0, since no two digits multiply to 100.
Dropping large products. Skipping every product above p instead of using the overflow column makes p = 0 answers wrong.
Allowing a leading 0. Starting row 1 from digit 0 would count numbers such as 05 as two-digit numbers.
Using i32 cells. For n = 12, p = 0 the answer, 617570463519, is far beyond i32.

Testing

n = 3, p = 6 gives 9.
n = 2, p = 12 gives 4: 26, 62, 34 and 43.
n = 3, p = 7 gives 3: 117, 171 and 711.
n = 2, p = 0 gives 9.
n = 12, p = 0 gives 617570463519.

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

Start learning free