LESSON 322 OF 347 · DYNAMIC PROGRAMMING

Digit Product Numbers in C#: Counting with 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 C#, explained

Problem overview

The method CountNumbers(int n, int p) returns how many base-10 numbers have exactly n digits and a digit product equal to p. The digit product is the result of multiplying all the digits together. A number cannot start with 0, so a 3-digit number runs from 100 to 999.

For n = 3 and p = 6 the answer is 9. Three digits multiply to 6 when they are some arrangement of 1, 2, 3 (six numbers: 123, 132, 213, 231, 312, 321) or of 1, 1, 6 (three numbers: 116, 161, 611).

The result is a long, because the counts get large quickly. With n = 12 there are 900 billion 12-digit numbers, and more than 600 billion of them contain a 0 digit, so the count for p = 0 does not fit in an int.

Approach: extend numbers one digit at a time

Trying every n-digit number would mean up to 900 billion checks. Instead, count numbers by their current digit product and grow them digit by digit. Appending digit d to a number with product j gives a longer number with product j * d. So the counts for length i + 1 depend only on the counts for length i.

That suggests a table where dp[i, j] is the number of i-digit numbers with digit product j. There is one wrinkle: products can grow far beyond p. A number whose product has already exceeded p can still end up at p only if a later 0 digit sends the product to 0, and that matters when p is 0. Because products only grow when multiplied by digits from 1 to 9, it is enough to track the products from 0 to p exactly and to lump everything larger than p into one extra column, p + 1.

This works since a product above p can only stay above p (times 1 to 9) or drop to 0 (times 0). It can never come back down to a value between 1 and p, so which exact large value it had never matters.

Step by step

Handle n = 0. A number has at least one digit, so nothing qualifies and the method returns 0. This also keeps row 1 from being missing: the table needs row 1 to exist.
Create the table. A long[,] with n + 1 rows and p + 2 columns: columns 0 to p for exact products and column p + 1 for "larger than p". C# zero-fills it.
Seed the 1-digit numbers. Loop i over the digits 1 to 9. A first digit cannot be 0.
Place each digit. The digit i has product i, so add 1 to dp[1, Math.Min(i, p + 1)]. A digit above p goes into the overflow column. It uses += because several digits can land in that same column when p is small.
Loop over lengths i from 1 to n - 1. Each pass reads row i and writes row i + 1.
Loop over every column j from 0 to p + 1, including column 0 (numbers containing a 0 digit) and the overflow column.
Try every next digit d from 0 to 9. Zero is allowed here, because only the first digit must be non-zero.
Find the new column. col = Math.Min(j * d, p + 1). For the overflow column this is still right: (p + 1) * d is at least p + 1 for d >= 1, and 0 for d = 0.
Add the counts. dp[i + 1, col] += dp[i, j]. An empty cell contributes 0, so no check is needed.
Return dp[n, p]. For n = 1 the loops do not run and row 1 already has the answer.

The solution in C#

class Solution {

    public long CountNumbers(int n, int p) {
        if (n == 0) {
            return 0;
        }
        long[,] dp = new long[n + 1, p + 2];
        for (int i = 1; i < 10; i++) {
            dp[1, Math.Min(i, p + 1)] += 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= p + 1; j++) {
                for (int d = 0; d < 10; ++d) {
                    int col = Math.Min(j * d, p + 1);
                    dp[i + 1, col] += dp[i, j];
                }
            }
        }
        return dp[n, p];
    }
}

Details worth knowing:

long counts, int index. The cells are long, but col is an int because it is used as an array index. The product j * d is computed in int, which is fine while p is small enough for the table to fit in memory.
Rectangular array. long[,] is a single block indexed as dp[i, j]. A jagged long[][] would need each row allocated separately.
+= 1 versus = 1. For p = 5, the digits 6, 7, 8 and 9 all map to column 6. Plain assignment would keep only one of them.
The clamp keeps indexes valid. Without Math.Min, j * d could be as large as 9 * (p + 1), past the last column.

Complexity

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

Space: O(n * p). The table has (n + 1) * (p + 2) long cells. Only two rows are ever read and written together, so two rows would suffice.

Edge cases and common mistakes

p = 0. Every number is "larger than 0" until it gets its first 0 digit. Dropping the overflow column would make the answer wrong, because those numbers must still be extended. For n = 2 the answer is 9: 10, 20, ..., 90.
n = 1. CountNumbers(1, 5) is 1, and CountNumbers(1, 0) is 0, because a 1-digit number cannot be 0 here: the first digit runs from 1 to 9.
A product no digits can make. With p = 11, which has a prime factor above 9, no number qualifies, and the table simply holds 0.
Using int for the table. The count for n = 12 and p = 0 is 617,570,463,519, well above int.MaxValue. In an int cell it would wrap around silently.
Allowing a leading 0. Seeding row 1 with digit 0 would count numbers such as 05 as 2-digit numbers.
Skipping column 0 in the loop. Numbers with a 0 digit keep growing, and each new digit keeps their product at 0.

Testing

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

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

Start learning free