Problem Description

Given a positive integer num, you need to find the smallest positive integer x such that when you multiply all the digits of x together, you get num.

For example:

• If num = 48, the answer would be 68 because 6 × 8 = 48
• If num = 15, the answer would be 35 because 3 × 5 = 15

The key requirements are:

1. Find the smallest such integer x
2. The product of all digits in x must equal num
3. If no valid answer exists, return 0
4. If the answer exceeds the range of a 32-bit signed integer (greater than 2^31 - 1), return 0

Special cases to consider:

• If num is 0, the answer is 10 (since 1 × 0 = 0)
• If num is 1, the answer is 1 itself
• If num contains prime factors other than 2, 3, 5, or 7, no valid answer exists (since digits can only be 1-9)

The solution works by greedily using the largest possible digits (9 down to 2) to factorize num, building the result from right to left to ensure the smallest possible number.

Intuition

To get the smallest number whose digits multiply to num, we need to think about what digits we can use and how to arrange them.

First, realize that we can only use digits 1-9 (0 would make the product 0). Since we want the smallest number, we want:

1. Fewer digits - A 2-digit number is smaller than a 3-digit number
2. Smaller leading digits - 234 is smaller than 432

The key insight is that to minimize the number of digits, we should use the largest possible digits. For example, if num = 24, we could use:

• 2 × 2 × 2 × 3 = 24 giving us 2223 (4 digits)
• 4 × 6 = 24 giving us 46 (2 digits)
• 3 × 8 = 24 giving us 38 (2 digits)

Between 46 and 38, we choose 38 because it's smaller.

This leads to our strategy: greedily extract the largest possible factors from 9 down to 2. Why this order?

• Using larger digits reduces the total number of digits needed
• By processing from 9 to 2, we ensure we use the maximum possible large digits

When building the answer, we place larger digits at the end (rightmost positions). This seems counterintuitive, but it ensures the smallest final number. For example, if we need digits 3 and 8:

• Placing 8 first then 3: 83
• Placing 3 first then 8: 38 ✓ (smaller)

The algorithm naturally handles this by building the number from right to left using ans = mul * i + ans, where each new digit i is placed to the left of previously added digits.

If after extracting all factors from 2-9, num is still greater than 1, it means num has prime factors larger than 7 (like 11, 13, etc.), which cannot be represented as single digits. In this case, no valid answer exists.

Learn more about Greedy and Math patterns.

Solution Approach

The implementation follows a greedy factorization approach:

1. Handle edge cases: If num < 2, return num directly. This covers cases where num = 0 or num = 1.

2. Initialize variables:

   • ans = 0: Stores the result number being built
   • mul = 1: A multiplier to help place digits in correct positions

3. Greedy factorization loop: Iterate through digits from 9 down to 2:

   for i in range(9, 1, -1):
       while num % i == 0:
           num //= i
           ans = mul * i + ans
           mul *= 10

   For each digit i:

   • Check if i divides num evenly using num % i == 0
   • If yes, extract this factor: num //= i
   • Add digit i to the left of current answer: ans = mul * i + ans
   • Update multiplier: mul *= 10 to shift position for next digit

   The formula ans = mul * i + ans effectively places the new digit i at the leftmost available position. For example:

   • Initially: ans = 0, mul = 1
   • Adding digit 8: ans = 1 * 8 + 0 = 8, mul = 10
   • Adding digit 6: ans = 10 * 6 + 8 = 68, mul = 100

4. Validation check: After the loop, verify:

   • num < 2: Ensures all factors were extracted (no prime factors > 7 remain)
   • ans <= 2**31 - 1: Ensures the answer fits in a 32-bit signed integer

   If both conditions are met, return ans; otherwise return 0.

The algorithm's correctness relies on:

• Processing larger digits first minimizes the total number of digits
• Building from right to left ensures the smallest numerical value
• The greedy approach guarantees the optimal solution because using the largest possible factors at each step minimizes both digit count and the resulting number's value

Example Walkthrough

Let's trace through the algorithm with num = 48:

Initial State:

• num = 48
• ans = 0 (our result number)
• mul = 1 (position multiplier)

Iteration Process (from digit 9 down to 2):

1. Check digit 9: 48 % 9 = 3 (not divisible) → skip

2. Check digit 8: 48 % 8 = 0 (divisible!)

   • Extract factor: num = 48 ÷ 8 = 6
   • Add digit 8 to answer: ans = 1 × 8 + 0 = 8
   • Update multiplier: mul = 10
   • Check again: 6 % 8 = 6 (not divisible) → move to next digit

3. Check digit 7: 6 % 7 = 6 (not divisible) → skip

4. Check digit 6: 6 % 6 = 0 (divisible!)

   • Extract factor: num = 6 ÷ 6 = 1
   • Add digit 6 to answer: ans = 10 × 6 + 8 = 68
   • Update multiplier: mul = 100
   • Check again: 1 % 6 = 1 (not divisible) → move to next digit

5. Check digits 5, 4, 3, 2: num = 1, so none divide evenly → skip all

Final Validation:

• num = 1 < 2 ✓ (all factors extracted successfully)
• ans = 68 ≤ 2^31 - 1 ✓ (within integer range)

Result: Return 68

Verification: 6 × 8 = 48 ✓

Notice how the algorithm builds the number from right to left: first placing 8, then placing 6 to its left, creating the smallest possible number whose digits multiply to 48.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log num)

The algorithm iterates through digits 9 to 2 (a constant 8 iterations in the outer loop). For each digit i, the inner while loop divides num by i as many times as possible. The total number of divisions across all digits is bounded by log num because we're repeatedly dividing the input number until it becomes less than 2. Each division operation takes O(1) time. Therefore, the overall time complexity is O(log num).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space. The variables ans, mul, and i are the only additional storage used, and they don't depend on the input size. No additional data structures like arrays or recursion stacks are used. Therefore, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Single-Digit Numbers

A common mistake is not properly handling when num itself is a single digit (2-9). The algorithm might unnecessarily try to factorize these numbers when they should be returned directly.

Pitfall Example:

# Incorrect: This would return 0 for num = 7
if num < 2:
    return num
# ... factorization logic ...
# After loop, num = 7 (not reduced to 1), so returns 0

Solution: Add a check for single-digit numbers before starting factorization:

if num < 10:
    return num

2. Building the Number in Wrong Order

Many implementations mistakenly build the number from left to right or use string concatenation, leading to larger results.

Pitfall Example:

# Wrong approach - builds left to right
result = 0
for digit in range(9, 1, -1):
    while num % digit == 0:
        num //= digit
        result = result * 10 + digit  # This gives larger numbers!

For num = 48: This would produce 86 instead of 68.

Solution: Always build from right to left using the formula result = position_multiplier * digit + result.

3. Missing Integer Overflow Check

Forgetting to check if the result exceeds the 32-bit signed integer limit (2^31 - 1 = 2147483647) can lead to incorrect outputs on platforms with strict integer bounds.

Pitfall Example:

# Missing overflow check
if num == 1:  # Only checking if factorization is complete
    return result

Solution: Always include the overflow check:

if num < 2 and result <= 2**31 - 1:
    return result

4. Incorrect Validation of Complete Factorization

Using num == 1 instead of num < 2 for the final check can cause issues with the edge case where num = 0.

Pitfall Example:

# Wrong: This fails for num = 0
if num == 1 and result <= 2**31 - 1:
    return result

Solution: Use num < 2 to handle both num = 1 (successful factorization) and num = 0 (edge case).

5. Not Handling num = 0 Correctly

The problem states that for num = 0, the answer should be 10 (since 1 × 0 = 0). However, the standard algorithm returns 0 directly for num < 2.

Pitfall Example: The current implementation returns 0 when num = 0, but according to the problem description, it should return 10.

Solution: Add explicit handling for num = 0:

if num == 0:
    return 10
if num == 1:
    return 1