LeetCode 625: Minimum Factorization

Problem Restatement

We are given a positive integer num.

We need to find the smallest positive integer x such that the product of the digits of x equals num.

If no such integer exists, return 0.

If the answer does not fit in a 32-bit signed integer, return 0.

The official examples are:

num = 48

Output:

68

because:

6 * 8 == 48

Another example:

num = 15

Output:

35

because:

3 * 5 == 15

Source: LeetCode 625 asks for the smallest positive integer whose digit product equals the input, returning 0 if impossible or outside 32-bit signed integer range.

Input and Output

Example function shape:

def smallestFactorization(num: int) -> int:
    ...

Examples

Example 1:

num = 48

We can factor 48 as:

6 * 8 = 48

So one valid number is:

68

The answer is:

68

Example 2:

num = 15

We can factor 15 as:

3 * 5 = 15

The smallest valid number is:

35

Example 3:

num = 11

There is no digit from 2 to 9 that can help build product 11.

The digit product cannot contain a prime factor 11.

So the answer is:

0

Example 4:

num = 1

The smallest positive integer whose digit product is 1 is:

1

So the answer is:

1

First Thought: Try All Numbers

A direct approach is to test numbers one by one.

For each number x, compute the product of its digits. If the product equals num, return x.

This is not practical.

The answer could be large, and checking every integer wastes time. We need to construct the answer from the factorization of num.

Key Insight

Every digit in the answer must be from 2 to 9, except for the special case num == 1.

The digit 1 does not change the product, but it makes the number longer and usually larger. So it is never useful for num > 1.

To make the final number as small as possible, we want as few digits as possible first. A number with fewer digits is smaller than any positive number with more digits, unless there are leading zeros, which we do not use here.

So we should use large digit factors whenever possible.

For example:

48 = 2 * 2 * 2 * 2 * 3

This could give:

22223

But we can combine factors into larger digits:

48 = 6 * 8

This gives:

68

So we greedily divide by digits from 9 down to 2.

After collecting the digits, we place them in ascending order to get the smallest number.

Algorithm

Handle the small case first.

If num == 1, return 1.

Then create an empty list called digits.

For each digit d from 9 down to 2:

1. While num is divisible by d, append d to digits.
2. Divide num by d.

After the loop:

1. If num != 1, then some factor could not be represented using digits 2 through 9. Return 0.
2. Reverse the collected digits so they are in ascending order.
3. Convert them into an integer.
4. If the integer is larger than 2^31 - 1, return 0.
5. Otherwise return the integer.

Correctness

For num == 1, the smallest positive integer with digit product 1 is 1, so returning 1 is correct.

For num > 1, digit 1 is never useful because multiplying by 1 does not change the product and only adds another digit to the answer. Therefore every useful digit must be in the range 2 to 9.

The greedy step tries larger digits first. This minimizes the number of digits because a larger composite digit can replace several smaller factors. For example, using 8 is better than using 2, 2, 2, because it preserves the same product with fewer digits. Similarly, using 9 is better than using 3, 3.

After all possible divisions by digits 9 down to 2, if the remaining num is greater than 1, then it contains a factor that cannot be represented by any digit from 2 to 9. No valid integer can have that digit product, so returning 0 is correct.

If the remaining num is 1, then the collected digits multiply to the original input. The greedy process used the fewest possible digits because it always replaced factors with the largest valid digit whenever possible.

Among numbers with the same multiset of digits, the smallest integer is obtained by placing digits in ascending order. Since we collected digits from large to small, reversing them gives the smallest possible arrangement.

Therefore the algorithm returns the smallest valid integer when one exists, and returns 0 when no valid integer exists or when the answer exceeds the 32-bit signed integer limit.

Complexity

The loop checks only digits 9 through 2, so the number of digit choices is constant.

Implementation

class Solution:
    def smallestFactorization(self, num: int) -> int:
        if num == 1:
            return 1

        digits = []

        for d in range(9, 1, -1):
            while num % d == 0:
                digits.append(d)
                num //= d

        if num != 1:
            return 0

        answer = 0

        for d in reversed(digits):
            answer = answer * 10 + d

            if answer > 2**31 - 1:
                return 0

        return answer

Code Explanation

The special case is handled first:

if num == 1:
    return 1

Then we collect digit factors:

digits = []

We try digits from 9 down to 2:

for d in range(9, 1, -1):

Whenever d divides num, we use it as one digit:

while num % d == 0:
    digits.append(d)
    num //= d

This extracts as many large digit factors as possible.

After the loop, if num is not 1, factorization failed:

if num != 1:
    return 0

Then we build the final number in ascending digit order:

for d in reversed(digits):
    answer = answer * 10 + d

The digits were collected from large to small, so reversing gives small to large.

The overflow check is done while building the answer:

if answer > 2**31 - 1:
    return 0

If the number fits, we return it:

return answer

Testing

def run_tests():
    s = Solution()

    assert s.smallestFactorization(48) == 68
    assert s.smallestFactorization(15) == 35
    assert s.smallestFactorization(1) == 1
    assert s.smallestFactorization(11) == 0
    assert s.smallestFactorization(36) == 49
    assert s.smallestFactorization(100) == 455
    assert s.smallestFactorization(2**31) == 0

    print("all tests passed")

run_tests()

Test meaning: