NeetCode #939LC-625MediumMath & Geometry
← Back to All Problems#939 · #625 · Minimum Factorization(最小因式分解)
📌 Problem Statement & Constraints
Given a positive integer
a, find the smallest positive integer b whose digit product equals a. Return 0 if no such b exists or if it exceeds the signed 32-bit range. Constraints: 1 <= a <= 2^31 - 1.💡 Core Algorithmic Approaches
- To minimise
b, minimise its number of digits and keep the most significant digits as small as possible. - Factor
aby trying divisors from 9 down to 2; using the largest factors first yields the fewest digits. - Prepending each found digit places the small digits in the most significant positions, which minimises the value.
- If
a < 10, thenb = aitself. If a factor greater than 9 remains, no digit decomposition exists and the answer is 0.
💻 Benchmark Python3 Implementation
class Solution:
def smallestFactorization(self, num: int) -> int:
if num < 10:
return num # a single digit is the answer
res = 0
mul = 1
for d in range(9, 1, -1): # largest factors first -> fewest digits
while num % d == 0:
num //= d
res += d * mul
mul *= 10
if num != 1: # a prime factor above 9 remains -> impossible
return 0
return res if res < 2 ** 31 else 0⚡ Complexity Deep Dive
⏱️ Time Complexity
O(log num): the number of factors is bounded by the digit count.
💾 Space Complexity
O(1): constant state.
⚠️ Interview Pitfalls & Follow-ups
- Factoring from 2 upward: it can produce more digits, e.g.
a = 24gives46instead of the smaller38. - Omitting the
num < 10base case: fora = 1the loop never runs andresstays 0, but the correct answer is 1. - Forgetting the overflow check: the constructed value can exceed
2^31 - 1. - Returning
reswhen a residual factor remains: the correct output is 0.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.