2847. Smallest Number With Given Digit Product

MediumGreedyMath
Leetcode Link

Problem Description

Given a positive integer n, the task is to find out the smallest positive integer whose digits multiply to give n. This problem boils down to figuring out what digits are needed and in what order they should be arranged to get the smallest possible number. If there is no such number that satisfies the condition, we return -1.

The important detail to note is that we're dealing with the multiplication of digits, so we need to use the factors of the given number n to construct the required smallest number. We also have to keep in mind that we aim to find the smallest such number, so we have to arrange the digits in ascending order (which is why we are checking divisibility from larger factors to smaller).

Intuition

The intuition behind the solution involves breaking down the given number into its prime factors, but with a twist. We'll need to factorize n in such a way that the factors are digits from 1 to 9.

We can leverage the fact that any positive integer can be factorized into prime factors. However, since we need the factors to be single digits, we use digits 2 to 9 (which are the only single-digit prime and composite numbers that can be factors of n).

The solution approach goes through the numbers 9 to 2 (in decreasing order) and checks whether they are factors of n. If any number i is a factor of n, then it's accounted for in the count array cnt, and n is divided by this factor i. This process is repeated until n is no longer divisible by i.

If at the end of the process, n is greater than 1, it means n had a factor that is not a digit (1 to 9), which implies no such number of single digits exists whose product is n. In this case, we return -1.

Otherwise, we construct the answer string by concatenating the factors in ascending order as many times as counted in cnt. The resultant string is the smallest number by digits whose product equals the original n. If no factors were used and n is reduced to 1, we simply return "1" as per the problem condition since 1 has no factors and it is the only case where the input number itself is the answer.

This solution ensures we always use the largest possible factors first, as this minimizes the total number of digits in the end result (since smaller digits need to be used more frequently to reach the same product).

Learn more about Greedy and Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Solution Approach

The solution follows these steps:

  1. Initialize a count array cnt of size 10: Elements of this array will represent how many times each digit from 2 to 9 divides n. We use a size 10 array for convenient indexing, even though indices 0 and 1 are not used.

    1cnt = [0] * 10

  2. Factorization Loop: Begin a loop from i = 9 down to i = 2. For each i, check if n is divisible by i. If it is, divide n by i, decrement n, and increment the count of i in cnt. Continue this process until n is no longer divisible by i.

    1for i in range(9, 1, -1):
2    while n % i == 0:
3        n //= i
4        cnt[i] += 1

  3. Final Check for Remaining n:

    • If n greater than 1: If after the factorization loop, n is still greater than 1, then n had a prime factor greater than 9, or another factor that is not a single digit, hence no such single-digit positive integer exists whose product is equal to n.

      1if n > 1:
2    return "-1"

    • If n equals 1: Construct the smallest number possible by concatenating the factors. String concatenation is used to repeatedly add each factor (i) to the result string (ans) the number of times it appears in cnt. To ensure the smallest possible number is formed, concatenation follows the ascending numerical order (from digit 2 to 9).

      1ans = "".join(str(i) * cnt[i] for i in range(2, 10))

  4. Return Result:

    • If ans is not empty, return it. It means we have found factors in the range 2 to 9 that multiply to n.

    • Otherwise, if ans is empty, it implies n was 1 to begin with since no factors were found in the loop. In this special case, the smallest number that can be formed is "1".

      1return ans if ans else "1"

The approach leverages digits as potential prime and composite factors and takes advantage of the properties of divisibility to decompose the number n into these factors. By iterating from higher to lower factors, it ensures that larger factors are used up first, minimizing the length of the final answer (as using more small factors would make the number longer). The data structure used is an array to keep track of the count of each factor, and the chosen algorithm is a backwards iteration combined with a greedy strategy for digit selection.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Example Walkthrough

Let's go through an example to illustrate the solution approach. Assume we are given the positive integer n = 36.

  1. Initialize the count array cnt: We start by initializing an array cnt of size 10 with all elements set to 0:

    1cnt = [0] * 10  # cnt = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

  2. Factorization Loop: We begin a loop from i = 9 down to i = 2. For the given n = 36:

    • Check i = 9: 36 is not divisible by 9, so we move to the next i.
    • Check i = 8: 36 is not divisible by 8, so we move to the next i.
    • Check i = 7: 36 is not divisible by 7, so we move to the next i.
    • Check i = 6: 36 is divisible by 6, so we divide n by 6 and increment cnt[6]. Now, n is 6, and cnt becomes [0, 0, 0, 0, 0, 0, 1, 0, 0, 0].
    • Now n is 6, we check again from i = 6 (which is a loop invariant condition), we find that 6 is divisible by 6, so we divide n by 6 and increment cnt[6] again. Now, n is 1, and cnt becomes [0, 0, 0, 0, 0, 0, 2, 0, 0, 0].

  3. Final Check for Remaining n:

    • If n greater than 1: This is not the case here; after factorization, n has been reduced to 1, so we move to the next step.

    • If n equals 1: We proceed to construct the smallest possible number by concatenating the factors. Our cnt array indicates that the digit 6 should appear twice.

      1ans = "".join(str(i) * cnt[i] for i in range(2, 10))  # ans = "66"

  4. Return Result: Since ans is not empty (it is "66"), this is the result we return.

The smallest positive integer whose digits multiply to give n = 36 is 66. Note how we used the larger factor (6) instead of smaller factors like 2 and 3 multiple times. This gave us the smallest number by digit count satisfying the required condition.

Solution Implementation

1class Solution:
2    def smallestNumber(self, num: int) -> str:
3        # Initialize a list to keep track of the count of digits (2 to 9)
4        digit_count = [0] * 10
5      
6        # Check for all prime factors of num from 9 to 2
7        # If the current digit divides num, keep dividing and increment the respective count
8        for digit in range(9, 1, -1):
9            while num % digit == 0:
10                num //= digit
11                digit_count[digit] += 1
12      
13        # If there's a leftover value in num greater than 1, it means num
14        # cannot be factored into the digits 2-9, so return "-1"
15        if num > 1:
16            return "-1"
17      
18        # Assemble the result string, comprising each digit multiplied by its count,
19        # sorted in ascending order to get the smallest number
20        result = "".join(str(i) * digit_count[i] for i in range(2, 10))
21      
22        # If result is empty (all counts are zero), return "1" since the smallest number
23        # that can be divided by these is 1
24        return result if result else "1"
25
1class Solution {
2
3    // Method to calculate the smallest number from the product of digits equal to n
4    public String smallestNumber(long n) {
5        // Array to count the occurrences of each digit from 2 to 9
6        int[] digitCount = new int[10];
7
8        // Iterate from digit 9 to 2
9        for (int i = 9; i > 1; --i) {
10            // Factor out the current digit from n as long as it divides n completely
11            while (n % i == 0) {
12                // Increment the count for the digit i
13                ++digitCount[i];
14                // Divide n by the digit i
15                n /= i;
16            }
17        }
18
19        // If n is greater than 1 at this point, it means n had a prime factor greater than 9
20        // which cannot be represented as a digit, hence return "-1"
21        if (n > 1) {
22            return "-1";
23        }
24
25        // StringBuilder to construct the smallest number
26        StringBuilder sb = new StringBuilder();
27
28        // Iterate over all digits from 2 to 9
29        for (int i = 2; i < 10; ++i) {
30            // Append each digit to the StringBuilder the number of times it appeared in the earlier step
31            while (digitCount[i] > 0) {
32                sb.append(i);
33                --digitCount[i];
34            }
35        }
36
37        // Obtain the final string answer from StringBuilder
38        String answer = sb.toString();
39      
40        // If the answer is empty, then n was either 1 or 0, both cases where '1' is the answer
41        return answer.isEmpty() ? "1" : answer;
42    }
43}
44
1class Solution {
2public:
3    // Function to find the smallest number with the given multiplicative factors
4    string smallestNumber(long long n) {
5        int digitCounts[10] = {}; // Array to store counts of each digit from 2 to 9
6
7        // Factorizes the number n by the digits from 9 to 2
8        for (int i = 9; i > 1; --i) {
9            while (n % i == 0) { // Check if i is a factor
10                n /= i; // Divide n by the factor i
11                ++digitCounts[i]; // Increment the count of the digit i in the result
12            }
13        }
14
15        // If after factorizing there is a remainder greater than 1,
16        // it means the number cannot be factorized into the digits 2-9
17        if (n > 1) {
18            return "-1"; // Return "-1" indicating it's not possible
19        }
20
21        string result; // String to store the result
22        // Construct the result from the digit counts
23        for (int i = 2; i < 10; ++i) {
24            // Append the digit i, digitCounts[i] number of times to the result
25            result += string(digitCounts[i], '0' + i);
26        }
27
28        // If the result is still an empty string, it means n was originally 1
29        // In this case, return "1"
30        return result.empty() ? "1" : result;
31    }
32};
33
1// Function to find the smallest number with the given multiplicative factors
2function smallestNumber(n: bigint): string {
3    // Array to store counts of each digit from 2 to 9
4    let digitCounts: number[] = new Array(10).fill(0);
5
6    // Factorizes the number n by the digits from 9 to 2
7    for (let i = 9; i > 1; --i) {
8        while (n % BigInt(i) === BigInt(0)) { // Check if i is a factor
9            n /= BigInt(i); // Divide n by the factor i
10            digitCounts[i]++; // Increment the count of the digit i in the result
11        }
12    }
13
14    // If after factorizing there is a remainder greater than 1,
15    // it means the number cannot be factorized into the digits 2-9
16    if (n > BigInt(1)) {
17        // Return a string indicating it's not possible
18        return "-1";
19    }
20
21    // String to store the result
22    let result = '';
23
24    // Construct the result from the digit counts
25    for (let i = 2; i < 10; ++i) {
26        // Append the digit i, digitCounts[i] times to the result
27        result += i.toString().repeat(digitCounts[i]);
28    }
29
30    // If the result is still an empty string, it means n was originally 1
31    // In this case, return "1"
32    return result || "1";
33}
34
Not Sure What to Study? Take the 2-min Quiz：

Which of these pictures shows the visit order of a depth-first search?

Time and Space Complexity

Time Complexity: The time complexity of the code is determined by the while loops that check for divisibility by numbers from 9 to 2. This process can occur at most O(log(n)) times for each divisor because after each iteration, n is divided by a number between 2 and 9, which reduces its size by at least a factor of 2. Since there are 8 possible divisors (from 9 to 2), the overall time complexity can be considered O(8 * log(n)), which simplifies to O(log(n)).

Space Complexity: The space complexity of the function is O(1). This is because the array cnt is of fixed size 10 (not dependent on the input size n), and the rest of the variables are of constant size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search is equivalent to which of the tree traversal order?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫