⚡Flashcard Drill➔
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

  1. To minimise b, minimise its number of digits and keep the most significant digits as small as possible.
  2. Factor a by trying divisors from 9 down to 2; using the largest factors first yields the fewest digits.
  3. Prepending each found digit places the small digits in the most significant positions, which minimises the value.
  4. If a < 10, then b = a itself. 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 = 24 gives 46 instead of the smaller 38.
  • Omitting the num < 10 base case: for a = 1 the loop never runs and res stays 0, but the correct answer is 1.
  • Forgetting the overflow check: the constructed value can exceed 2^31 - 1.
  • Returning res when 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.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems