Problem overview
The method countNumbers(_ n: Int, _ p: Int) 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 six arrangements of the digits 1, 2, 3 (123, 132, 213, 231, 312, 321) and the three arrangements of 1, 1, 6 (116, 161, 611). The notes give N <= 12, so there are up to 9 * 10^11 candidates, far too many to test one by one.
Approach: track the product so far
When you append a digit d to a number, its digit product is multiplied by d. So all that matters about a prefix is how many digits it has and what its product is. Let dp[i][j] be the number of i-digit numbers with digit product j. Row 1 is easy: the digits 1 to 9. Row i + 1 comes from row i: for each product j and each digit d from 0 to 9, the count in dp[i][j] moves to the column for j * d.
There is one problem: the product can grow huge, and the table can't have a column for every value. Only products up to p matter, but products above p can't simply be thrown away. Consider p = 0. Every number starts with a non-zero product, and only a later 0 digit turns it into 0. If the large products were dropped, those numbers would be lost. So the table gets one extra column, p + 1, meaning "the product is greater than p". From there, multiplying by 1 to 9 stays above p, and multiplying by 0 gives product 0.
A small example, n = 2 and p = 2. Row 1 is [0, 1, 1, 7]: one number with product 1 (the digit 1), one with product 2, and seven digits (3 to 9) in the "above 2" column. In row 2, column 2 collects the digit 1 times 2 and the digit 2 times 1, so the answer is 2: the numbers 12 and 21.
Step by step
- Handle
n == 0. A number has at least one digit, so return 0. This also protects the code below: the table writes into row 1, which would not exist. - Create the table as a
var:n + 1rows andp + 2columns, covering products 0 topand the extra columnp + 1. - Loop
iover1..<10, the digits 1 to 9, because a number can't start with 0. - Fill row 1 with
dp[1][min(i, p + 1)] += 1. A digit's product is the digit itself, and any digit larger thanpgoes into columnp + 1. Use+=, because for a smallpseveral digits share that column. - Loop
iover1..<n. Each pass extends the finished rowiby one digit, and the last pass fills rown. - Loop
jover0...p + 1, every column, including 0 (numbers that contain a 0 digit) and the overflow column. - Loop
dover0..<10. Zero is allowed here, since only the first digit has to be non-zero. - Compute the target column as
min(j * d, p + 1). - Add the count forward:
dp[i + 1][col] += dp[i][j]. Empty cells hold 0, so no check is needed. - Return
dp[n][p]. Forn = 1the loops over rows never run, and row 1 already holds the answer.
The solution in Swift
class Solution {
func countNumbers(_ n: Int, _ p: Int) -> Int {
if n == 0 {
return 0
}
var dp = Array(repeating: Array(repeating: 0, count: p + 2), count: n + 1)
for i in 1..<10 {
dp[1][min(i, p + 1)] += 1
}
for i in 1..<n {
for j in 0...p + 1 {
for d in 0..<10 {
let col = min(j * d, p + 1)
dp[i + 1][col] += dp[i][j]
}
}
}
return dp[n][p]
}
}
Swift details worth knowing:
- Why the early return matters. For
n = 0,1..<nwould be1..<0. A half-open range whose lower bound is above its upper bound stops the program with a run-time error. Withn = 1the range1..<1is empty and harmless. - Precedence in
0...p + 1. The arithmetic operator binds tighter than the range operator, so this means0...(p + 1). - Reusing the name
i. The twofor iloops are separate scopes, so the secondidoes not clash with the first. - No overflow here.
Intis 64 bits and arithmetic overflow crashes in Swift. The productj * dis at most9 * (p + 1)beforemintrims it, so it is safe for any sensiblep.
Complexity
Time: O(n * p). There are n rows, p + 2 columns, and 10 digits per cell, so about 10 * n * (p + 2) operations.
Space: O(n * p). The table holds (n + 1) * (p + 2) integers. Only two rows are alive at once, so it could be reduced to O(p).
Edge cases and common mistakes
p = 0. The answer counts numbers that contain at least one 0 digit. Forn = 2that is 10, 20, ..., 90, so 9. This case is why the overflow column exists.n = 1.pfrom 1 to 9 gives 1, andp = 0gives 0, because 0 is not counted as a 1-digit number here.pwith a prime factor above 7. No digit can supply that factor. Forn = 2andp = 11the answer is 0.- Allowing a leading zero. Filling row 1 from 0 would count strings like
06as 2-digit numbers. - Dropping products above
p. It looks harmless but gives wrong answers forp = 0, as explained above. - Using
=instead of+=in row 1. Withp = 2the digits 3 to 9 all land in column 3, and the count would be 1 instead of 7.
Testing
n = 3,p = 6gives9.n = 2,p = 0gives9.n = 3,p = 1gives1, the number 111.n = 2,p = 7gives2: 17 and 71.n = 1,p = 5gives1.n = 0,p = 5gives0.
