Start learning free

LESSON 323 OF 348 · DYNAMIC PROGRAMMING

Numbers with Digit Product P in Kotlin: 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
    Ctrl + Enter to check

    KOTLIN · DYNAMIC PROGRAMMING

    Digit Product Numbers in Kotlin, explained

    Problem overview

    The function countNumbers(n, p) 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 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 can be 1, 2 and 3 in any order, which gives 6 numbers (123, 132, 213, 231, 312, 321), or 1, 1 and 6 in any order, which gives 3 more (116, 161, 611). The notes say N <= 12, and the return type is Long because counts grow past what an Int can hold.

    Approach: track the product so far, with one bucket for "too big"

    Checking every number with n digits means up to 900 billion candidates for n = 12, which is far too slow. Instead, build numbers one digit at a time and count how many numbers share the same product. 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 row i + 1 can be computed from row i.

    The product can grow huge (nine 9s give 387,420,489), but only products up to p matter, because digits can't bring a product back down except by a 0. The table therefore gets one extra column, p + 1, that stands for "the product is larger than p". It is needed rather than optional: a number with a 0 digit has product 0, and a product that is above p today still turns into 0 when a 0 digit arrives. When p is 0, every number starts above p and is rescued only by a 0 digit later.

    A product above p stays above p when multiplied by 1 to 9, so those digits keep the number in the extra column, and a 0 digit sends it to column 0. That is why the same formula, "multiply and cap at p + 1", works for every column.

    Step by step

    1. Handle n == 0. A number has at least one digit, so there is nothing to count. Return 0 before building the table, which would otherwise write into a row 1 that doesn't exist.
    2. Create the table as n + 1 rows of LongArray(p + 2): columns 0 to p for exact products, and column p + 1 for "bigger than p".
    3. Fill row 1. Loop over the digits 1 to 9 (the first digit can't be 0). The digit i alone has product i, so add 1 to column minOf(i, p + 1). Use +=: when p is small, several digits land in the extra column.
    4. Extend row by row. Loop i from 1 until n. Each pass reads the finished row i and fills row i + 1.
    5. Loop over every column j from 0 to p + 1, including the extra one and column 0.
    6. Try every digit d from 0 to 9. Zero is allowed here, because only the first digit is restricted.
    7. Compute the new column. col is minOf(j * d, p + 1).
    8. Pass the count forward. Add dp[i][j] to dp[i + 1][col]. If no number has product j, the cell holds 0 and adding it changes nothing, so no check is needed.
    9. Return dp[n][p]. For n = 1 the loops don't run and row 1 is already the answer.

    The solution in Kotlin

    class Solution {

    fun countNumbers(n: Int, p: Int): Long {
        if (n == 0) {
            return 0
        }
        val dp = Array(n + 1) { LongArray(p + 2) }
        for (i in 1 until 10) {
            dp[1][minOf(i, p + 1)] += 1
        }
        for (i in 1 until n) {
            for (j in 0..p + 1) {
                for (d in 0 until 10) {
                    val col = minOf(j * d, p + 1)
                    dp[i + 1][col] += dp[i][j]
                }
            }
        }
        return dp[n][p]
    }
}

    The Kotlin details worth a closer look:

    • Long for counts. The result type is Long, and so are the table cells. For n = 12 and p = 0 the answer is 617570463519, far beyond the 2,147,483,647 an Int holds. An Int table would wrap around silently instead of reporting an error.
    • Returning a literal. return 0 in a function returning Long compiles: Kotlin treats the integer literal as a Long because the expected type is known.
    • += 1 on a LongArray element. The literal 1 is also read as a Long here.
    • Ranges. 1 until 10 is the digits 1 to 9. 0..p + 1 includes p + 1, which is the extra column, because the range operator has lower precedence than +. 0 until 10 is the digits 0 to 9.
    • j * d is an Int product. The column index is at most (p + 1) * 9, so it overflows only for a p above 200 million, where the table itself would no longer fit in memory.

    Complexity

    Time: O(n * p). There are n - 1 passes, each over p + 2 columns and 10 digits, so about 10 * n * (p + 2) steps.

    Space: O(n * p). The table has (n + 1) * (p + 2) cells. Only two rows are alive at a time, so two rows would be enough if memory mattered.

    Edge cases and common mistakes

    • Two-digit numbers with a zero. countNumbers(2, 0) returns 9: the numbers 10, 20, up to 90. Numbers like 01 don't count, since the first digit can't be 0.
    • All twelve digits, product zero. countNumbers(12, 0) returns 617570463519, which is 900000000000 numbers minus the 282429536481 numbers with no 0 digit at all (nine choices for each of the twelve digits).
    • One digit. countNumbers(1, 5) returns 1. countNumbers(1, 0) returns 0, since 0 is not a one-digit number here.
    • A product no number reaches. countNumbers(2, 100) returns 0, because 100 can't be written as a product of two digits.
    • Dropping the extra column. Without it, p = 0 breaks: numbers like 5 followed by 0 would be lost along the way.
    • Starting digits at 0. Looping 0 until 10 in row 1 would count numbers with a leading zero.
    • Using Int cells. The answers for large n and small p wrap around.

    Testing

    • n = 3, p = 6 gives 9.
    • n = 2, p = 7 gives 2 (17 and 71).
    • n = 3, p = 1 gives 1 (111).
    • n = 4, p = 1 gives 1 (1111).
    • n = 2, p = 0 gives 9.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free