LeetCode 625 - Minimum Factorization

LeetCode Problem 625

Difficulty: 🟡 Medium
Topics: Math, Greedy

Solution

Problem Understanding

The problem asks us to find the smallest positive integer x such that the product of all of its digits equals the given integer num.

In other words, we want to decompose num into a multiplication of decimal digits from 1 to 9, then arrange those digits to form the numerically smallest possible integer.

For example:

• If num = 48, we can express it as 6 × 8 = 48, producing the number 68.
• Another valid decomposition is 2 × 3 × 8 = 48, producing 238, but 68 < 238, so 68 is the correct answer.

The important detail is that we are not minimizing the number of digits alone, we are minimizing the resulting integer value. Since shorter numbers are usually smaller than longer numbers, we generally want fewer digits, but digit arrangement also matters.

The input is a single positive integer num, where:

• 1 <= num <= 2^31 - 1

The output should be:

• The smallest positive integer whose digits multiply to num
• 0 if no such integer exists
• 0 if the result exceeds the 32-bit signed integer range

The constraint is important because num can be very large, up to approximately 2.1 billion. A brute-force search through candidate numbers would be infeasible.

There are several important edge cases:

• If num is a single digit from 1 to 9, the answer is simply num, since that digit already satisfies the condition.
• Some numbers cannot be factorized into digits 2 through 9. For example, 11 is prime and larger than 9, so there is no valid answer.
• The resulting number might exceed the 32-bit signed integer limit (2,147,483,647), even if a valid digit factorization exists.

Approaches

Brute Force Approach

A brute-force solution would try every positive integer x, compute the product of its digits, and check whether it equals num.

For each candidate number:

1. Extract all digits.
2. Multiply them together.
3. Compare the result with num.
4. Stop when the first valid number is found.

This works because eventually we would discover the smallest valid number if one exists.

However, this approach is prohibitively slow. The search space is enormous because there is no practical upper bound on how many numbers we may need to check before finding a solution. Even for moderate values of num, the number of candidates becomes astronomically large.

We need a mathematical observation to avoid exhaustive search.

Key Insight

Instead of searching through numbers, we can think in reverse:

We want digits whose product equals num.

Since digits can only be 2 through 9 for meaningful multiplication, we should repeatedly divide num by the largest possible digit first, from 9 down to 2.

Why largest first?

Using larger factors reduces the total number of digits. Fewer digits generally create a smaller integer. However, because we want the numerically smallest final integer, we collect larger factors first and later reverse their order when constructing the number.

For example:

48

• Divide by 8 → remaining 6
• Divide by 6 → remaining 1

Collected digits: [8, 6]

To make the smallest integer, arrange them in ascending order:

68

If after removing all factors from 9 to 2, we still have a number greater than 1, then some prime factor exceeds 9, meaning no valid digit decomposition exists.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential / impractical	O(1)	Checks candidate integers one by one
Optimal Greedy Factorization	O(log n)	O(log n)	Factorize using digits 9 to 2

Algorithm Walkthrough

1. Handle the special case where num is less than 10.

If num is already a single digit, it is trivially the smallest valid answer because the digit itself multiplies to num. 2. Create an empty list to store digit factors.

We will repeatedly extract digit factors from 9 down to 2. 3. Iterate from digit 9 down to 2.

For each digit:

• While num is divisible by the digit:

• Add the digit to the list.

• Divide num by that digit.

This greedily extracts the largest possible digit factors. 4. Check whether factorization succeeded.

After processing all digits, if num is still greater than 1, then it contains a prime factor larger than 9, so no valid answer exists. Return 0. 5. Construct the smallest number.

Since larger digits were collected first, reverse the order while building the final number.

For example:

[8, 6] → 68

We construct the integer digit by digit. 6. Check 32-bit overflow.

If the result exceeds 2^31 - 1, return 0. 7. Return the constructed integer.

Why it works

The greedy strategy works because larger digit factors compress the factorization into fewer digits. A number with fewer digits is almost always numerically smaller than one with more digits. After greedily extracting larger digits, arranging them in ascending order guarantees the lexicographically smallest possible number among all valid factorizations.

The algorithm succeeds whenever num can be completely factorized into digits 2 through 9. If any remaining factor is greater than 9, no valid digit representation exists.

Python Solution

class Solution:
    def smallestFactorization(self, num: int) -> int:
        if num < 10:
            return num

        digits = []

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

        if num != 1:
            return 0

        result = 0

        for digit in reversed(digits):
            result = result * 10 + digit

        return result if result <= 2**31 - 1 else 0

The implementation begins by handling the simplest case, when num is already a single digit. In that situation, the answer is immediate.

Next, we create a list called digits to store extracted digit factors. The loop runs from 9 down to 2, greedily dividing num whenever possible.

The nested while loop is important because a digit factor may appear multiple times. For example, 72 can be divided by 8 and then again by 3.

After factorization, we verify whether num became 1. If not, some remaining prime factor cannot be represented as a decimal digit.

Finally, we reconstruct the answer by traversing the collected digits in reverse order, producing the smallest valid integer. Before returning, we verify that the result fits within a 32-bit signed integer.

Go Solution

func smallestFactorization(num int) int {
	if num < 10 {
		return num
	}

	digits := []int{}

	for digit := 9; digit >= 2; digit-- {
		for num%digit == 0 {
			digits = append(digits, digit)
			num /= digit
		}
	}

	if num != 1 {
		return 0
	}

	result := 0
	maxInt32 := 2147483647

	for i := len(digits) - 1; i >= 0; i-- {
		result = result*10 + digits[i]

		if result > maxInt32 {
			return 0
		}
	}

	return result
}

The Go implementation follows the exact same greedy strategy as the Python solution.

One Go-specific difference is explicit overflow handling. Since Go integers vary by architecture, we compare against the constant 2147483647 directly to enforce the LeetCode requirement of a signed 32-bit integer.

The digit storage uses a slice ([]int), which dynamically grows as factors are appended. Reversing is handled using an index loop from the end of the slice.

Worked Examples

Example 1

Input: num = 48

We greedily divide by digits from 9 to 2.

Step	Digit Tried	num Before	Action	num After	Digits
1	9	48	Not divisible	48	[]
2	8	48	Divide by 8	6	[8]
3	7	6	Not divisible	6	[8]
4	6	6	Divide by 6	1	[8, 6]

Now num = 1, so factorization succeeded.

Reverse digits:

[8, 6] → [6, 8]

Construct number:

• 0 × 10 + 6 = 6
• 6 × 10 + 8 = 68

Final answer: 68

Example 2

Input: num = 15

Step	Digit Tried	num Before	Action	num After	Digits
1	9	15	Not divisible	15	[]
2	8	15	Not divisible	15	[]
3	7	15	Not divisible	15	[]
4	6	15	Not divisible	15	[]
5	5	15	Divide by 5	3	[5]
6	3	3	Divide by 3	1	[5, 3]

Reverse digits:

[5, 3] → [3, 5]

Construct number:

• 0 × 10 + 3 = 3
• 3 × 10 + 5 = 35

Final answer: 35

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Each successful division reduces num, so the total divisions are logarithmic
Space	O(log n)	Stores extracted digit factors

The loop over digits 9 through 2 is constant size, only eight iterations. The dominant cost comes from repeated division. Since num shrinks multiplicatively after every successful division, the total number of operations is logarithmic in num.

The auxiliary space comes from storing extracted factors. In the worst case, num repeatedly divides by 2, producing logarithmically many digits.

Test Cases

solution = Solution()

assert solution.smallestFactorization(48) == 68  # Provided example
assert solution.smallestFactorization(15) == 35  # Provided example

assert solution.smallestFactorization(1) == 1  # Minimum input
assert solution.smallestFactorization(9) == 9  # Single digit input
assert solution.smallestFactorization(10) == 25  # 2 * 5 = 10
assert solution.smallestFactorization(12) == 26  # 2 * 6 = 12

assert solution.smallestFactorization(11) == 0  # Prime > 9, impossible
assert solution.smallestFactorization(13) == 0  # Another impossible case

assert solution.smallestFactorization(36) == 49  # Greedy optimization
assert solution.smallestFactorization(72) == 89  # 8 * 9 = 72

assert solution.smallestFactorization(100) == 455  # 4 * 5 * 5 = 100
assert solution.smallestFactorization(180) == 459  # 4 * 5 * 9 = 180

assert solution.smallestFactorization(2147483647) == 0  # Large prime-like case

Test Summary

Test	Why
48 → 68	Validates provided example
15 → 35	Validates provided example
1 → 1	Minimum boundary value
9 → 9	Single digit case
10 → 25	Basic composite factorization
12 → 26	Multiple valid decompositions
11 → 0	Impossible prime factor
13 → 0	Another impossible case
36 → 49	Ensures greedy minimization
72 → 89	Larger factor preference
100 → 455	Multiple repeated factors
180 → 459	Composite with several digits
2147483647 → 0	Large edge case

Edge Cases

Single Digit Inputs

When num is between 1 and 9, the answer should simply be num. A buggy implementation might unnecessarily factorize these values and accidentally return a different number. The implementation avoids this by immediately returning num when num < 10.

Impossible Factorizations

Numbers like 11 or 13 contain prime factors larger than 9. Since digits are restricted to decimal digits, these cannot be represented as products of digits. After greedy division, the implementation checks whether num == 1. If not, it correctly returns 0.

32-bit Integer Overflow

Even when a valid digit factorization exists, the resulting integer might exceed the signed 32-bit range. Returning such a value would violate the problem specification. The implementation explicitly verifies that the constructed number does not exceed 2,147,483,647 and returns 0 if overflow occurs.