MediumNo. 0625LeetCode Premium
Minimum Factorization — LeetCode 625 Python Solution
- Pattern
- Greedy
- Topics
- Greedy, Math
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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
- Input
- num = 48
- Output
- 68
Python solution
class Solution:
def smallestFactorization(self, num: int) -> int:
if num < 2:
return num
ans, mul = 0, 1
for i in range(9, 1, -1):
while num % i == 0:
num //= i
ans = mul * i + ans
mul *= 10
return ans if num < 2 and ans <= 2**31 - 1 else 0Complexity
- Time
- O(n log n)
- Space · auxiliary
- O(1) to O(n)
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 625. Minimum Factorization is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0670 | Maximum Swap | Medium |
| 0738 | Monotone Increasing Digits | Medium |
| 0910 | Smallest Range II | Medium |
| 0976 | Largest Perimeter Triangle | Easy |
| 0991 | Broken Calculator | Medium |
| 1217 | Minimum Cost to Move Chips to The Same Position | Easy |
Frequently asked questions
- How hard is LeetCode 625. Minimum Factorization?
LeetCode 625. Minimum Factorization is rated Medium on LeetCode.
- What topics does LeetCode 625. Minimum Factorization cover?
LeetCode 625. Minimum Factorization is tagged Greedy and Math on LeetCode.
- Is LeetCode 625. Minimum Factorization a premium problem?
Yes. LeetCode 625. Minimum Factorization is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.