Teaching Kids Programming – Smallest Number With Given Digit Product (Greedy Factorization Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a positive integer n, return a string representing the smallest positive integer such that the product of its digits is equal to n, or “-1” if no such number exists.

Example 1:
Input: n = 105
Output: “357”
Explanation: 3 * 5 * 7 = 105. It can be shown that 357 is the smallest number with a product of digits equal to 105. So the answer would be “105”.

Example 2:
Input: n = 7
Output: “7”
Explanation: Since 7 has only one digit, its product of digits would be 7. We will show that 7 is the smallest number with a product of digits equal to 7. Since the product of numbers 1 to 6 is 1 to 6 respectively, so “7” would be the answer.

Example 3:
Input: n = 44
Output: “-1”
Explanation: It can be shown that there is no number such that its product of digits is equal to 44. So the answer would be “-1”.

Constraints:
1 <= n <= 10^18

Smallest Number With Given Digit Product (Greedy Factorization Algorithm)

TLDR; The number shouldn’t have 1, because we can just remove it and get a smaller number. We only need to consider factors between 2 to 9 inclusive (only 1 single digit). We want to have a larger digit factor on the right, and a less digit e.g. 2, on the left. Thus, we can greedly factorize the digits from 9 to 2.

The problem “Smallest Number With Given Digit Product” sounds like a mouthful, but it’s not as complicated as it might seem at first glance. Here, we’ll dive deep into a Python solution for this problem and unpack the logic behind it.

Problem Statement

Given an integer n, return the smallest number whose digits multiply to n. If there is no such number, return -1.

For instance, if n = 36, the answer is 49 since 4 * 9 = 36.

Solution Walkthrough

Let’s go step-by-step through the provided Python solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def smallestNumber(self, n: int) -> str:
        if n == 1:
            return str(n)
 
        arr = []
        for i in range(9, 1, -1):
            while n % i == 0:
                arr.append(i)
                n //= i
 
        if not arr or n != 1:
            return "-1"
        return "".join(map(str, reversed(arr)))

class Solution:
    def smallestNumber(self, n: int) -> str:
        if n == 1:
            return str(n)

        arr = []
        for i in range(9, 1, -1):
            while n % i == 0:
                arr.append(i)
                n //= i

        if not arr or n != 1:
            return "-1"
        return "".join(map(str, reversed(arr)))

If n equals 1

If n is 1, the smallest number that gives a product of 1 is 1 itself. Thus, the code directly returns “1”.

Constructing the number

For the smallest number, we would want the digits to be as small as possible and as far to the left as possible (i.e., higher place values). To achieve this, the logic tries to break n down using the largest single-digit factors first. That’s why there’s a loop that starts from 9 and goes down to 2 (for i in range(9, 1, -1)).

Inside the loop

If n is divisible by i (n % i == 0), we store this number in the arr list, as it’s one of the digits of the smallest number.

After storing the digit, we divide n by i (n //= i) to get the next value of n that we need to factorize.

Checking for Invalid Cases

If after this process n is not 1, it means there are prime factors of n that are greater than 9 or n itself is a prime number greater than 9 (e.g., 11, 13, 17). In such cases, it’s impossible to represent n as a product of single digits, and we return “-1”.

Constructing the Result

If the process is successful, we reverse the arr list because we want smaller digits on the higher place values. Finally, we join the digits and return them as a string.

Conclusion

This problem is a beautiful blend of mathematics and coding. It demands understanding how numbers can be broken down into their prime factors and then manipulating those factors to derive the desired solution. The provided Python solution offers an efficient way to tackle this problem.

–EOF (The Ultimate Computing & Technology Blog) —