Skip to main content
Talentd

Minimum Factorization - Solution & Explanation

MediumPremiumFree on FleetCodeMathGreedy4 min readAsked at: Tencent
Practice this problem

Problem Statement

Given a positive integer num, return the smallest positive integer x whose multiplication of each digit equals num. If there is no answer or the answer is not fit in 32-bit signed integer, return 0.

 

Example 1:

Input: num = 48
Output: 68

Example 2:

Input: num = 15
Output: 35

 

Constraints:

  • 1 <= num <= 231 - 1

Approach Overview

Problem Overview: Given a positive integer a, construct the smallest positive integer whose digits multiply to a. If no such integer exists or the result exceeds a 32-bit signed integer, return 0.

Approach 1: Brute Force Search (Exponential Time, O(1) Space)

The direct idea is to try integers starting from 1, compute the product of their digits, and check if it equals a. For each candidate number, iterate through its digits and multiply them together. The first valid match is the smallest number because numbers are checked in increasing order. This approach is impractical because the search space grows extremely fast, making the time complexity exponential relative to the number of digits.

Approach 2: Greedy Digit Factorization (O(log a) Time, O(log a) Space)

The key observation: any valid number must be composed of digits 2 to 9 whose product equals a. Instead of searching numbers, factor a using the largest digits first. Iterate from digit 9 down to 2, repeatedly dividing a whenever the digit is a factor. Each successful division adds that digit to the result. Using larger digits first reduces the total digit count, which guarantees the final number is minimal once digits are reversed into ascending order.

If after factoring a the remainder is greater than 1, no valid digit combination exists and the answer is 0. Finally, rebuild the number from the collected digits and verify it fits within the 32‑bit signed integer range.

This solution relies on math properties of factorization and a simple greedy strategy: always pick the largest valid digit to minimize the resulting integer length. The number of divisions is bounded by the number of factors, which is roughly O(log a).

Recommended for interviews: The greedy factorization approach. Interviewers expect you to recognize that digit products correspond to factors between 2 and 9. Starting from 9 ensures fewer digits, which directly produces the smallest numeric value after reversing. Mentioning the brute force idea briefly shows you considered the naive search before optimizing with a greedy mathematical insight.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SearchExponentialO(1)Conceptual baseline to understand the problem; not practical for large values
Greedy Digit FactorizationO(log a)O(log a)Optimal solution for production or interviews; uses digit factors 9→2 to minimize result length

Video Solution

625. Minimum Factorization (Leetcode Medium) • Programming Live with Larry • 452 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Minimum Factorization easy or hard?
Minimum Factorization is typically rated Medium difficulty. The implementation is short, but recognizing the greedy factorization idea is the main challenge. Once you identify that digits 2–9 represent factors of the product, the rest of the solution becomes straightforward.
Minimum Factorization Python/Java solution
Most implementations iterate digits from 9 to 2 and repeatedly divide the number while possible. The digits are stored in a list, then reversed to construct the smallest integer. The same logic works across Python, Java, C++, and Go with O(log a) time complexity.
How to solve Minimum Factorization in O(log n)?
Factor the number using digits 9 through 2. For each digit, repeatedly divide the input while it remains divisible and store that digit. After processing all digits, rebuild the number from the collected digits in reverse order. If the remainder is greater than 1 or the result exceeds a 32-bit integer, return 0.
What is the best approach for Minimum Factorization?
The optimal solution uses greedy digit factorization. Divide the number by digits from 9 down to 2 and collect those digits whenever they evenly divide the value. This minimizes the total digit count and guarantees the smallest resulting integer. The approach runs in O(log a) time because the value shrinks with each division.
Is Minimum Factorization asked at Google/Amazon/Meta?
Minimum Factorization represents a typical math and greedy interview problem seen in coding interviews at large tech companies. Variants of digit factorization or greedy decomposition appear in interviews at companies like Google, Amazon, and Meta because they test number reasoning and optimization.
What data structure is used in Minimum Factorization?
The solution mainly uses simple variables and often a list or stack to store the digits extracted during factorization. After collecting digits, they are reversed or appended to build the final integer. No complex data structures are required beyond basic arrays or strings.
What is the time complexity of Minimum Factorization?
The greedy factorization algorithm runs in O(log a) time since each successful division reduces the number. The space complexity is also O(log a) because the resulting digits must be stored before forming the final integer. Brute force alternatives are exponential and impractical.

Ready to solve this problem?

Practice Minimum Factorization with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer