Start learning free

LESSON 347 OF 414 · DYNAMIC PROGRAMMING

Numbers with Digit Product P in Scala: 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

    SCALA · DYNAMIC PROGRAMMING

    Digit Product Numbers in Scala, 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 can't start with 0, and the notes limit n to 12.

    For n = 3 and p = 6 the answer is 9. The digits must multiply to 6, which happens for the digit sets {1, 2, 3} (six orders: 123, 132, 213, 231, 312, 321) and {1, 1, 6} (three orders: 116, 161, 611).

    The method returns a Long. Among 12-digit numbers, 617,570,463,519 contain a zero digit, and their product is 0, so for p = 0 the answer is far beyond the range of Int.

    Approach: grow the number one digit at a time

    There are 9 * 10^11 numbers with 12 digits, too many to test one by one. Instead, count how many numbers of each length reach each product, and extend them digit by digit.

    Let dp(i)(j) be the number of i-digit numbers whose digit product is j. Appending a digit d to such a number multiplies its product by d, so the count flows from dp(i)(j) into dp(i + 1)(j * d).

    Products can grow past p, and the table can't have a column for every possible product. So the table has one extra column, p + 1, that stands for "greater than p". A product above p stays above p when it is multiplied by a digit from 1 to 9, and becomes 0 when it is multiplied by 0. That is the reason for the extra column rather than just discarding such numbers: when p is 0, a number whose product is already huge still ends up at 0 as soon as a zero digit is appended.

    Take n = 2 and p = 7. Row 1 has a 1 in each of the columns 1 to 7, and a 2 in column 8 (the "above 7" column), because the digits 8 and 9 are larger than 7. In row 2, column 7 receives the count from column 1 with digit 7, and from column 7 with digit 1. Those are the numbers 17 and 71, so the answer is 2.

    Step by step

    1. Handle n = 0. A number has at least one digit, so return 0. This also protects the table, whose row 1 only exists when n is at least 1.
    2. Create the table as an Array.ofDim[Long] with n + 1 rows and p + 2 columns. The columns are products 0 to p plus the "above p" column. The cells are Long because the counts outgrow Int.
    3. Loop over the first digit with 1 until 10. The digits are 1 to 9, because a number can't start with 0.
    4. Fill row 1: add 1 to dp(1)(math.min(i, p + 1)). A single digit is its own product. Digits larger than p all land in column p + 1, which is why the update uses += and not =.
    5. Loop over the lengths with 1 until n. Pass i extends row i into row i + 1.
    6. Loop over the products with 0 to p + 1, including column 0 (numbers with a zero digit) and the "above p" column.
    7. Try every appended digit d from 0 to 9. Zero is allowed here, since only the first digit is restricted.
    8. Find the destination column: col = math.min(j * d, p + 1).
    9. Move the count: add dp(i)(j) to dp(i + 1)(col). If no number has product j, the cell holds 0 and the addition changes nothing.
    10. Return dp(n)(p). For n = 1 the loop over lengths doesn't run, and row 1 already holds the answer.

    The solution in Scala

    class Solution {

    def countNumbers(n: Int, p: Int): Long = {
        if (n == 0) {
            return 0
        }
        val dp = Array.ofDim[Long](n + 1, p + 2)
        for (i <- 1 until 10) {
            dp(1)(math.min(i, p + 1)) += 1
        }
        for (i <- 1 until n) {
            for (j <- 0 to p + 1) {
                for (d <- 0 until 10) {
                    val col = math.min(j * d, p + 1)
                    dp(i + 1)(col) += dp(i)(j)
                }
            }
        }
        return dp(n)(p)
    }
}

    Some Scala details in this code:

    • Long against Int. An Int holds values up to about 2.1 billion and wraps silently past that. The 12-digit count of 617,570,463,519 needs a Long, which is 64 bits. The method's return type, the table's element type and the Array.ofDim[Long] call all have to agree.
    • return 0 in a Long method. The literal 0 is an Int, and Scala widens it to Long automatically, so this compiles.
    • += 1 and += dp(i)(j) on array cells update the cell in place. Adding an Int literal to a Long cell is fine.
    • Early return. Scala usually leaves the result as the last expression, but an early exit before the table is built is one of the places where return is natural.
    • Nested loops over ranges. 1 until 10 gives 1 to 9, 0 until 10 gives 0 to 9, and 0 to p + 1 includes p + 1. Each for introduces a fresh variable, so the two uses of i in the two loops don't clash: the first i is out of scope by the time the second begins.

    Complexity

    Time: O(n * p). For each of the n - 1 extension rounds, the loops visit p + 2 products and 10 digits. That is a constant 10 times n * p operations.

    Space: O(n * p). The table has (n + 1) * (p + 2) cells. Each row depends only on the previous one, so two rows would be enough.

    Edge cases and common mistakes

    • p = 0. Every number with a zero digit counts. countNumbers(2, 0) returns 9: the numbers 10, 20, ..., 90. With one digit the answer is 0, since a leading zero isn't allowed and countNumbers(1, 0) returns 0.
    • Dropping the "above p" column. For p = 0, the table would lose every number like 51 whose product is positive until a later 0 appears. The answers for 3 or more digits would be too small.
    • Using = in row 1. With p below 9, several digits map to column p + 1. Plain assignment keeps only the last one.
    • Appending only 1 to 9. The appended digit may be 0. Only the first digit is restricted, and without a zero option the case p = 0 returns 0 for every length.
    • n = 1. countNumbers(1, 5) returns 1 (the digit 5), and a digit product larger than 9, such as countNumbers(1, 12), returns 0.
    • Large products. A product that no digits can reach gives 0. For example countNumbers(2, 12) is 4 (26, 34, 43, 62), while a prime like 11 is impossible and gives 0.
    • Index overflow in j * d. j is at most p + 1 and d at most 9, so the product is safe for any p that fits in memory as a table.

    Testing

    • n = 3, p = 6 gives 9.
    • n = 2, p = 7 gives 2.
    • n = 2, p = 0 gives 9.
    • n = 1, p = 5 gives 1.
    • n = 0, p = 5 gives 0.
    • n = 12, p = 0 gives 617570463519.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free