We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Factorization

Number: 625

Difficulty: Medium

Paid? Yes

Companies: Tencent

Problem Description

Given a positive integer num, the task is to return the smallest positive integer x whose digits multiply to num. If no such positive integer exists or if the result does not fit in a 32-bit signed integer, return 0. For example, if num = 48, the smallest such x is 68 since 6 * 8 = 48, and if num = 15, the result is 35.

Key Insights

  • When num is 1, the answer is 1 because 1 is the only digit whose product is 1.
  • Factorize num by trying to divide it by digits from 9 down to 2.
  • Each time a digit divides num, add it as a factor and update num.
  • If after division num is not 1 then it means there is no valid combination, so return 0.
  • Sorting the extracted digits in ascending order will yield the smallest possible integer.

Space and Time Complexity

Time Complexity: O(log(num)) – The process divides num repeatedly by factors between 2 and 9. Space Complexity: O(1) – Only a constant amount of additional space is used to store factors.

Solution

The solution uses a greedy algorithm combined with factorization. The main idea is to break the integer num into factors that are digits between 2 and 9. We iterate from 9 down to 2 and check if the current candidate divides num evenly. Each candidate digit found is stored in a list. After processing, if num is not reduced to 1, it indicates that a proper factorization is not possible (for example, when a prime factor greater than 9 is involved). Then, sort the list of factors to form the smallest possible number. Finally, if the resulting number is larger than the maximum 32-bit signed integer, we return 0.

The key data structure used is a list (or array) to store the factors. The algorithm's greedy approach ensures that we use larger digits first so that when sorted in ascending order the resulting number is the smallest possible.

Code Solutions

# Python solution for Minimum Factorization
def smallestFactorization(num):
    # If num is less than 10, then it is already a single digit.
    if num < 10:
        return num
    
    # List to store extracted factors/digits.
    factors = []
    
    # For each possible digit candidate from 9 down to 2.
    for candidate in range(9, 1, -1):
        # While candidate evenly divides num we record the candidate digit.
        while num % candidate == 0:
            factors.append(candidate)
            num //= candidate
    
    # If num is not 1 after factorization, a valid combination doesn't exist.
    if num != 1:
        return 0
    
    # Sort the factors to form the smallest possible number.
    factors.sort()
    
    # Build the number from the sorted digits.
    result = 0
    for digit in factors:
        result = result * 10 + digit
        # Check if the number exceeds the 32-bit signed integer limit.
        if result > 2**31 - 1:
            return 0
    
    return result

# Example usage:
#print(smallestFactorization(48)) # Should output 68
#print(smallestFactorization(15)) # Should output 35
← Back to All Questions