Problem Description

Given a positive integer n, you need to find the smallest positive integer whose digits, when multiplied together, give the product n. If no such number exists, return "-1".

For example:

• If n = 48, the answer would be "68" because 6 × 8 = 48, and "68" is the smallest number whose digit product equals 48
• If n = 15, the answer would be "35" because 3 × 5 = 15
• If n = 1, the answer would be "1" because the product of digits of "1" is 1
• If n = 11, the answer would be "-1" because 11 is a prime number and cannot be expressed as a product of single digits (1-9)

The key insight is that you want to construct the smallest number possible, which means:

1. Using the fewest digits possible
2. Placing smaller digits at the beginning of the number

The solution works by factoring n into digits from 2 to 9. It starts from 9 and works downward, greedily extracting as many of each digit as possible. This ensures we use larger digits (which reduces the total number of digits needed) while building the result from smallest to largest digits (which gives us the numerically smallest answer).

If after factoring out all possible digits from 2-9, there's still a remainder greater than 1, it means n has a prime factor greater than 9, making it impossible to represent as a product of single digits.

Intuition

To find the smallest number whose digit product equals n, we need to think about what digits can multiply to give us n. Since we can only use digits 1-9, we need to decompose n into factors that are all single digits.

The first observation is that if n contains any prime factor greater than 7 (like 11, 13, 17, etc.), it's impossible to create such a number because these primes can't be expressed as products of digits 1-9. This immediately tells us when to return "-1".

Next, to make the resulting number as small as possible, we want:

1. Fewer digits - A 2-digit number is always smaller than a 3-digit number with the same digit sum
2. Smaller digits in front - For numbers with the same length, placing smaller digits at the beginning makes the number smaller (e.g., 239 < 329)

This leads us to a greedy strategy: use the largest possible digits (to minimize the count of digits), but arrange them in ascending order (to get the smallest number).

Why start factoring from 9 down to 2? Consider n = 24:

• We could use 2 × 2 × 2 × 3 = 24, giving us "2223"
• Or we could use 8 × 3 = 24, giving us "38"
• Or we could use 4 × 6 = 24, giving us "46"

The second and third options are clearly better because they use fewer digits. By greedily extracting 9s first, then 8s, then 7s, and so on, we ensure we're using the largest possible digits, which minimizes the total digit count.

After extracting all factors from 9 down to 2, if there's any remainder greater than 1, it must be a prime factor greater than 9, making the problem unsolvable. The special case where n = 1 is handled by returning "1" when no factors were found.

Learn more about Greedy and Math patterns.

Solution Approach

The solution uses prime factorization combined with a greedy approach to construct the smallest possible number.

Step 1: Factor out digits from 9 to 2

We use an array cnt of size 10 to count how many times each digit appears in our result. Starting from digit 9 and working down to 2, we check if n is divisible by that digit:

for i in range(9, 1, -1):
    while n % i == 0:
        n //= i
        cnt[i] += 1

This greedy approach ensures we use the largest possible digits first, minimizing the total number of digits needed. For example, if n = 24:

• Check 9: not divisible
• Check 8: 24 % 8 == 0, so we divide and get n = 3, cnt[8] = 1
• Check 7, 6, 5, 4: not divisible
• Check 3: 3 % 3 == 0, so we divide and get n = 1, cnt[3] = 1

Step 2: Check for impossible cases

After factoring, if n > 1, it means there's a prime factor greater than 9 remaining, making it impossible to express as a product of single digits:

if n > 1:
    return "-1"

Step 3: Construct the result string

We build the answer by concatenating digits from 2 to 9 (smallest to largest) according to their counts:

ans = "".join(str(i) * cnt[i] for i in range(2, 10))

This ensures the smallest possible number because smaller digits appear first. For our example with n = 24, we'd get "38" (3 appears before 8).

Step 4: Handle special case

If the answer string is empty (which happens when n = 1), we return "1":

return ans if ans else "1"

The key insight is that by factoring from largest to smallest (9 to 2) but building the result from smallest to largest (2 to 9), we achieve both goals: minimum digit count and smallest numerical value.

Example Walkthrough

Let's walk through the solution with n = 48:

Step 1: Factor out digits from 9 to 2

Starting with n = 48 and an empty count array cnt = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]:

• Check digit 9: 48 % 9 = 3 (not divisible), skip
• Check digit 8: 48 % 8 = 0 (divisible!)
  • n = 48 ÷ 8 = 6, cnt[8] = 1
• Check digit 7: 6 % 7 = 6 (not divisible), skip
• Check digit 6: 6 % 6 = 0 (divisible!)
  • n = 6 ÷ 6 = 1, cnt[6] = 1
• Check digits 5, 4, 3, 2: n = 1, so no more divisions possible

After factoring: n = 1, cnt = [0, 0, 0, 0, 0, 0, 1, 0, 1, 0]

Step 2: Check for impossible cases

Since n = 1 (not greater than 1), we can proceed. If n were still greater than 1, it would mean we have a prime factor > 9, making the problem impossible.

Step 3: Construct the result string

Build the answer by placing digits from smallest to largest:

• Start from digit 2: cnt[2] = 0, add nothing
• Digit 3: cnt[3] = 0, add nothing
• Digit 4: cnt[4] = 0, add nothing
• Digit 5: cnt[5] = 0, add nothing
• Digit 6: cnt[6] = 1, add "6"
• Digit 7: cnt[7] = 0, add nothing
• Digit 8: cnt[8] = 1, add "8"
• Digit 9: cnt[9] = 0, add nothing

Result: "68"

Step 4: Handle special case

Since our answer string is not empty, we return "68".

Verification: 6 × 8 = 48 ✓

This gives us the smallest possible number whose digit product equals 48. Note how using larger digits (6 and 8) instead of smaller ones (like 2, 2, 2, 2, 3 which also multiply to 48) gives us fewer total digits, and arranging them in ascending order gives us the smallest numerical value.

Solution Implementation

Time and Space Complexity

The time complexity is O(log n). This is because the algorithm iterates through digits 9 to 2 (a constant 8 iterations), and for each digit i, it performs division operations while n % i == 0. The total number of divisions across all digits is bounded by log n since we're repeatedly dividing n by factors between 2 and 9. In the worst case where n is a power of 2, we would perform log₂ n divisions.

The space complexity is O(1). The algorithm uses a fixed-size array cnt of length 10 to count occurrences of each digit, which requires constant space. The string construction at the end creates an output string, but when analyzing space complexity for the algorithm itself (excluding the output), we only consider the auxiliary space used, which remains constant regardless of the input size n.

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

Common Pitfalls

1. Incorrect Factorization Order

One common mistake is factoring from smallest to largest digits (2 to 9) instead of largest to smallest:

Wrong approach:

for digit in range(2, 10):  # Wrong order!
    while n % digit == 0:
        n //= digit
        digit_count[digit] += 1

Why it fails: For n = 12, this would give us "2223" (using 2×2×3) instead of the optimal "26" (using 2×6). The greedy approach must use larger composite digits first to minimize the total digit count.

Correct approach: Always factor from 9 down to 2 to prioritize larger digits.

2. Forgetting the Special Case n = 0

The problem states n is a positive integer, but if extended to handle n = 0:

Incomplete handling:

if n == 0:
    return "10"  # Common mistake: returning "0"

Why it matters: The digit product of "0" is 0, but "10" (1×0=0) would be the smallest multi-digit number with product 0. However, since the problem specifies positive integers only, this edge case should be validated at the input level.

3. Building Result in Wrong Order

After factorization, concatenating digits in descending order instead of ascending:

Wrong construction:

result = "".join(str(digit) * digit_count[digit] for digit in range(9, 1, -1))

Why it fails: For n = 48, this would give us "86" instead of "68". The smallest number requires smaller digits to appear first (leftmost positions have higher place values).

4. Not Handling n = 1 Correctly

Forgetting that when n = 1, the result should be "1", not an empty string:

Missing edge case:

# Without the special case handling
return result  # Returns "" when n = 1

Solution: Always check if the result is empty and return "1" in that case:

return result if result else "1"

5. Integer Overflow in Other Languages

While Python handles arbitrary precision integers, in languages like Java or C++:

Potential issue:

// In Java, this might overflow for large n
int n = input;
while (n % digit == 0) {
    n /= digit;
    // ...
}

Solution: Use appropriate data types (long in Java, long long in C++) or implement string-based multiplication for very large inputs.