Domain 2MediumCORE

Minimum Factorization

We are given a positive integer a. We need to find the smallest positive integer b such that if we multiply all digits of b, the result equals a. If no such number exists (e.g., prime factors > 9) or the resulting number exceeds the maximum value for a signed 32-bit integer ($2^{31} - 1$), return 0.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Math#Recursion

625. Minimum Factorization

Model: qwen3.5:9b
Topics: Math,Recursion
FAANG asked: 0
Acceptance rate: 33.0%


Problem Breakdown

We are given a positive integer a. We need to find the smallest positive integer b such that if we multiply all digits of b, the result equals a. If no such number exists (e.g., prime factors > 9) or the resulting number exceeds the maximum value for a signed 32-bit integer (231−12^{31} - 1), return 0.

Inputs:

  • Integer a (> 0).

Outputs:

  • Smallest positive integer b.
  • Return 0 if impossible or overflow occurs.

Constraints & Edge Cases:

  • Digit Limit: Digits of b must be between 1 and 9 (digit 0 is not allowed because it would make the product 0, but input a > 0).
  • Overflow: The resulting number cannot exceed 231−12^{31} - 1. Python handles large integers automatically, so we must explicitly check this limit before returning.
  • Prime Factors: If a has a prime factor greater than 9 (e.g., input is 17), it’s impossible to form using single digits; return 0.

Intuition

First thought: I could iterate through every integer starting from 1 and check if the product of its digits equals a. However, this brute-force approach has a time complexity proportional to the magnitude of b, which is exponential relative to input size in terms of digit count. It’s inefficient.

The key insight here is that we are essentially factorizing a into single-digit components (2 through 9). To minimize the resulting number b:

  1. Minimize Digit Count: A smaller number has fewer digits. Since d1×d2=ad_1 \times d_2 = a, using larger factors reduces the total count of digits needed to reach product a. For example, for 48, 6×86 \times 8 (two digits) is better than 3×?3 \times ?. So we should greedily divide by the largest possible digit (9 down to 2).
  2. Minimize Value: Once we have a set of factors that multiply to a with minimal count, their order matters for value. To make the number smallest, smaller digits must be placed at higher place values (left side) and larger digits at lower place values (right side).

So the strategy is: Greedily extract largest possible factors from 9 down to 2, then sort them ascendingly to construct b. If any remainder remains after extracting all valid digit factors (>1), it’s impossible. Finally, check for overflow.

Approach

  1. Handle Base Cases: Check if a is 0 or 1 (though input says positive). For this specific problem variant, usually a=1 results in output 1. If the loop logic handles division by digits >9 correctly, we just need to ensure prime factors are handled.
  2. Greedy Factorization: Iterate from digit d = 9 down to 2. While a % d == 0, append d to a list and update a //= d. This ensures we use the largest possible digits first, minimizing total count.
  3. Check Feasibility: After checking all single-digit factors (down to 1), if a > 1, it means there is a prime factor larger than 9 that cannot be represented by any digit product. Return 0.
  4. Construct Number: Sort the collected digits in ascending order and join them into a string, then convert back to integer.
  5. Overflow Check: Compare result against 2**31 - 1. If larger, return 0.

Complexity Analysis

  • Time Complexity: O(log⁡9N)O(\log_{9} N) or effectively constant relative to input value magnitude because we only divide by digits up to 9. In terms of number of bits in the output integer b, it is linear with respect to the number of digits, which is logarithmic w.r.t a.
  • Space Complexity: O(D)O(D) where D is the number of digits in the result (stored in a list). Since max 32-bit int has ~10 digits, this is effectively O(1)O(1).

Solution

def smallestNumber(a: int) -> int:
    # Handle edge case for input 1. Product of digit '1' is 1.
    if a == 1: 
        return 1
    
    factors = []
    
    # Greedily divide by largest possible digits (9 down to 2)
    # This minimizes the total number of digits required.
    for i in range(9, 1, -1):
        while a % i == 0:
            factors.append(i)
            a //= i
            
    # If 'a' is still greater than 1 after dividing by all single digit factors,
    # it implies there's a prime factor > 9 (e.g., input was 23). Impossible.
    if a != 1: 
        return 0
        
    # Sort digits ascending to place smaller values at higher significance positions
    factors.sort()
    
    # Construct the number string and convert back to int
    result = int("".join(map(str, factors)))
    
    # Check for signed 32-bit integer overflow limit (2^31 - 1)
    if result > 2**31 - 1: 
        return 0
        
    return result

# Example usage / Test cases implied by problem description
print(smallestNumber(48))   # Output: 68
print(smallestNumber(15))   # Output: 35

Edge Cases Handled

  • Input a = 1: Returns 1 immediately, as a single digit ‘1’ satisfies the product constraint.
  • Prime Factors > 9: If input is prime (e.g., 23) or composite with large factors (e.g., 47), the loop finishes and a != 1, returning 0.
  • Overflow: The constructed integer is explicitly compared against 231−12^{31} - 1. Python’s arbitrary precision integers prevent runtime errors, but we return 0 if it exceeds the limit.
  • Digit Zero: Logic implicitly avoids digit ‘0’ because dividing by 9 down to 2 never includes 0, and multiplying digits including 0 would result in product 0 (which contradicts input > 0).