LESSON 314 OF 338 · DYNAMIC PROGRAMMING

Numbers With Digit Product P in Go: Counting with a Capped DP Table

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

GO · DYNAMIC PROGRAMMING

Digit Product Numbers in Go, explained

Problem overview

The method countNumbers(n, p) returns how many base-10 numbers with exactly n digits have 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. The digits can be 1, 2 and 3 in any order (six numbers), or 1, 1 and 6 in any order (three numbers). The notes allow n up to 12, which is far too many numbers to test one by one: a 12-digit number has 900 billion candidates.

Approach: count by length and product

A number with i + 1 digits is a number with i digits plus one more digit on the right. Appending a digit d multiplies the product by d. So the product of the longer number depends only on the product of the shorter one and on d, and that suggests a table: dp[i][j] is the number of i-digit numbers whose digit product is j.

Products can grow huge (nine 9s multiply to 387,420,489), but only the value p matters in the end. Once a product is greater than p, it can only come back down to a meaningful value by being multiplied by 0, which turns it into 0. So all products above p are merged into one extra column, p + 1, which means "bigger than p". The table has p + 2 columns: products 0 to p, plus the overflow column.

That merge is safe. A product above p multiplied by a digit 1 to 9 stays above p, and multiplied by 0 becomes 0, so column p + 1 transitions the same way as every individual large product would. It is also needed: when p is 0, every number has a product above 0 until its first 0 digit appears.

For n = 3 and p = 6 the first two rows are:

length 1: [0 1 1 1 1 1 1 3]
length 2: [9 1 2 2 3 2 4 67]

The columns are the products 0 to 6 and the overflow column. In row 1 the digits 7, 8 and 9 all land in the overflow column, which therefore holds 3. In row 2, column 6 holds 4 (the numbers 16, 61, 23 and 32), and column 0 holds 9 (10, 20, ..., 90).

Step by step

Handle n == 0 first. There is nothing to count, so return 0. The code below also writes into row 1, which exists only when n is at least 1.
Allocate the table: n + 1 rows, each created with its own make of p + 2 zeros.
Fill row 1. A 1-digit number is one of the digits 1 to 9, because the first digit can't be 0.
Place each digit in its column. The digit i has product i, or goes to column p + 1 if it is larger than p. Use +=: when p is small, several digits share the overflow column.
Extend row by row. With i from 1 to n - 1, each pass reads the finished row i and fills row i + 1.
Visit every column j from 0 to p + 1, including the overflow column and column 0 (numbers that contain a 0 digit).
Try every appended digit d from 0 to 9. A 0 is fine here: only the first digit must be non-zero, and row 1 took care of that.
Find the target column: col := min(j*d, p+1).
Add the count: dp[i+1][col] += dp[i][j]. An empty cell adds 0, so no check is needed.
Return dp[n][p]. For n = 1 the loop doesn't run and row 1 already holds the answer.

The solution in Go

type Solution struct{}

func (s Solution) countNumbers(n int, p int) int {
	if n == 0 {
		return 0
	}
	dp := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, p+2)
	}
	for i := 1; i < 10; i++ {
		dp[1][min(i, p+1)] += 1
	}
	for i := 1; i < n; i++ {
		for j := 0; j <= p+1; j++ {
			for d := 0; d < 10; d++ {
				col := min(j*d, p+1)
				dp[i+1][col] += dp[i][j]
			}
		}
	}
	return dp[n][p]
}

Go details worth a closer look:

if without parentheses. The condition has no parentheses and the braces are mandatory, even for a one-line body.
Rows need their own make. make([][]int, n+1) gives n + 1 nil slices; indexing one would panic until the loop allocates it.
Built-in min. Since Go 1.21 it works on integers without an import. Here it caps both a single digit and a product at p + 1.
Declaring col with :=. It exists only inside the innermost loop body, and each iteration gets a fresh one. An unused col would be a compile error.
Integer width. int is 64 bits here. With p = 0 and n = 12 the answer is 617,570,463,519, the count of 12-digit numbers that contain a 0. It needs more than 32 bits, and it fits easily in a 64-bit int.

Complexity

The loops run n, p + 2 and 10 times, so the time is O(n * p) with a factor of 10 for the digits. The table holds (n + 1) * (p + 2) integers, so the space is O(n * p) too. The cost grows with the value of p, not with the number of candidate numbers.

Edge cases and common mistakes

p = 0. The answer is the number of n-digit numbers with at least one 0 digit. For n = 2 that is 9 (10, 20, ..., 90). Dropping the overflow column would make this case come out wrong, because every number starts with a nonzero product.
n = 1. countNumbers(1, 5) is 1, and countNumbers(1, 0) is 0, since the single-digit number 0 isn't an n-digit number under the lesson's rule that the first digit is non-zero. countNumbers(1, 10) is also 0.
p = 1. Only numbers made of 1s qualify, so the answer is 1 for every n.
Using = for row 1. Digits above p share column p + 1, so the first assignment would be overwritten.
Leaving out the digit 0 in the extension loop. Numbers such as 101 would never be built.
Allowing a leading zero. Looping the first digit from 0 would count shorter numbers as if they had n digits.

Testing

Try (2, 6), which is 4 (16, 61, 23, 32), and (2, 7), which is 2 (17 and 71). (3, 6) gives the lesson's 9, and (3, 0) gives 171.

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

Start learning free