LeetCode Problem 2847

Difficulty: 🟡 Medium
Topics: Math, Greedy

Solution

LeetCode 2847 - Smallest Number With Given Digit Product

Problem Understanding

The problem gives us a positive integer n and asks us to construct the smallest positive integer whose digits multiply together to exactly n.

For example, if n = 105, we need to find some integer whose digits have product 105. One valid choice is 357 because:

3 × 5 × 7 = 105

The goal is not simply to find any such integer, but the numerically smallest one.

The input is a single positive integer:

1 <= n <= 10^18

The upper bound is extremely large. Since n can be as large as one quintillion, we cannot enumerate candidate numbers and test their digit products. Any solution must work directly with the mathematical properties of digit multiplication.

A few important observations immediately follow from the constraints:

• Digits can only be from 0 to 9.
• Since the desired number must be positive, leading zeros are not allowed.
• Every digit contributing to the product must be between 1 and 9.
• If n contains a prime factor larger than 7, then no solution exists because no decimal digit has such a prime factor.
• The special case n = 1 needs careful handling. The smallest positive integer whose digit product is 1 is simply "1".

Some edge cases that can easily cause mistakes include:

• n = 1
• Single digit values such as 7
• Values containing large prime factors, such as 11 or 44
• Large powers such as 2^60
• Numbers whose factorization requires many digits

The problem guarantees that n is positive, so we never need to handle zero or negative inputs.

Approaches

Brute Force

A brute force solution would generate positive integers in increasing order and compute the product of their digits until one matches n.

For each candidate number:

1. Extract all digits.
2. Compute their product.
3. Compare with n.

This approach is correct because eventually every positive integer would be examined, and the first matching one would indeed be the smallest.

However, it is completely impractical. Even for modest values of n, the desired answer could be very large, and the search space grows exponentially. With n up to 10^18, brute force is hopeless.

Key Insight

Every digit from 2 to 9 can be viewed as a factor:

Digit	Prime Factorization
2	2
3	3
4	2²
5	5
6	2×3
7	7
8	2³
9	3²

Instead of building numbers directly, we can factorize n using digits.

To minimize the resulting number, we want to use as few digits as possible, because numbers with fewer digits are always smaller than numbers with more digits when there are no leading zeros.

The largest digits provide the most compression. Therefore, we repeatedly divide n by digits from 9 down to 2.

For example:

n = 72

72 ÷ 9 = 8
8 ÷ 8 = 1

digits = [9, 8]

The product is:

9 × 8 = 72

To obtain the smallest numerical value, we sort these digits in ascending order:

89

This greedy strategy is optimal because larger digits combine multiple smaller factors into a single digit, minimizing the digit count. Once all factors are collected, arranging them in ascending order produces the smallest possible number.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential / unbounded	O(1)	Enumerates candidate numbers until a match is found
Optimal	O(log n)	O(log n)	Greedily factorizes using digits 9 down to 2

Algorithm Walkthrough

1. Handle the special case where n == 1. The answer is "1" because the product of the digits of 1 equals 1.
2. Create an empty list to store digits that will form the answer.
3. Iterate through candidate digits from 9 down to 2.
4. While the current digit divides n, repeatedly:

• Append the digit to the answer list.
• Divide n by that digit.

5. After processing all digits from 9 to 2, check whether n has become 1.
6. If n is not 1, some remaining factor cannot be represented by any decimal digit. In that case return "-1".
7. Otherwise, the collected digits multiply to the original value.
8. The digits were collected from largest to smallest. Reverse the list so that digits appear in ascending order.
9. Convert the digits into a string and return it.

Why it works

The greedy choice of using the largest possible digit first is optimal because larger digits combine multiple prime factors into a single digit. This minimizes the total number of digits required. Any solution with fewer digits is numerically smaller than any solution with more digits when all digits are positive.

Once the minimum digit count is achieved, arranging those digits in ascending order produces the smallest possible number among all permutations of the same digits. Therefore the algorithm always returns the smallest valid integer.

Python Solution

class Solution:
    def smallestNumber(self, n: int) -> str:
        if n == 1:
            return "1"

        digits = []

        for digit in range(9, 1, -1):
            while n % digit == 0:
                digits.append(str(digit))
                n //= digit

        if n != 1:
            return "-1"

        digits.reverse()
        return "".join(digits)

The implementation begins with the special case n == 1.

The digits list stores the factors chosen by the greedy process. We iterate from 9 down to 2, repeatedly dividing whenever possible. This extracts the largest digit factors first and naturally minimizes the number of digits needed.

After all divisions are complete, a remaining value larger than 1 indicates that some prime factor greater than 7 remains, making a solution impossible.

The collected digits are currently in descending order because they were extracted from largest to smallest. Reversing them places them in ascending order, which yields the smallest numerical value. Finally, the digits are concatenated into the answer string.

Go Solution

func smallestNumber(n int64) string {
	if n == 1 {
		return "1"
	}

	digits := make([]byte, 0)

	for digit := int64(9); digit >= 2; digit-- {
		for n%digit == 0 {
			digits = append(digits, byte('0'+digit))
			n /= digit
		}
	}

	if n != 1 {
		return "-1"
	}

	for left, right := 0, len(digits)-1; left < right; {
		digits[left], digits[right] = digits[right], digits[left]
		left++
		right--
	}

	return string(digits)
}

The Go implementation follows exactly the same greedy factorization strategy.

The digits are stored as a []byte, which is efficient because each factor corresponds directly to a character digit. After factor extraction, the slice is reversed in place and converted to a string.

Since the input constraint is at most 10^18, int64 safely holds all intermediate values.

Worked Examples

Example 1

Input:

n = 105

Factorization process:

Current n	Chosen Digit	New n	Digits
105	7	15	[7]
15	5	3	[7, 5]
3	3	1	[7, 5, 3]

Collected digits:

[7, 5, 3]

Reverse:

[3, 5, 7]

Result:

"357"

Example 2

Input:

n = 7

Factorization process:

Current n	Chosen Digit	New n	Digits
7	7	1	[7]

Reverse:

[7]

Result:

"7"

Example 3

Input:

n = 44

Factorization process:

Current n	Chosen Digit	New n	Digits
44	4	11	[4]

No digit from 9 through 2 can divide 11.

Final state:

n = 11

Since n != 1, the factor 11 cannot be represented using decimal digits.

Result:

"-1"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Each successful division reduces n by at least a factor of 2
Space	O(log n)	The answer may contain O(log n) digits

The loop only checks the fixed set of digits from 9 to 2, so the dominant work comes from repeated divisions. Every division shrinks n substantially, yielding a logarithmic running time. The storage requirement is proportional to the number of digits in the final answer, which is also logarithmic in n.

Test Cases

sol = Solution()

assert sol.smallestNumber(105) == "357"      # provided example
assert sol.smallestNumber(7) == "7"          # single digit answer
assert sol.smallestNumber(44) == "-1"        # impossible due to factor 11

assert sol.smallestNumber(1) == "1"          # special case
assert sol.smallestNumber(2) == "2"          # smallest nontrivial factor
assert sol.smallestNumber(9) == "9"          # largest single digit

assert sol.smallestNumber(10) == "25"        # 2 * 5
assert sol.smallestNumber(12) == "26"        # 2 * 6
assert sol.smallestNumber(18) == "29"        # 2 * 9

assert sol.smallestNumber(36) == "49"        # 4 * 9
assert sol.smallestNumber(72) == "89"        # 8 * 9

assert sol.smallestNumber(11) == "-1"        # prime > 7
assert sol.smallestNumber(13) == "-1"        # another impossible prime
assert sol.smallestNumber(17) == "-1"        # another impossible prime

assert sol.smallestNumber(64) == "88"        # 8 * 8
assert sol.smallestNumber(100) == "455"      # 4 * 5 * 5

assert sol.smallestNumber(2**20) == "88888844"  # large power of two

Test Summary

Test	Why
105	Provided example
7	Single digit answer
44	Impossible composite number
1	Special case
2	Smallest factorable value
9	Largest single digit
10	Product of two primes
12	Uses compressed factor 6
18	Uses compressed factor 9
36	Multiple valid representations, verify smallest
72	Demonstrates greedy compression
11	Prime greater than 7
13	Another impossible prime
17	Another impossible prime
64	Repeated large digit factor
100	Mix of composite and prime factors
2^20	Stress test with many divisions

Edge Cases

Edge Case 1, n = 1

This case is easy to overlook because the factorization loop would never add any digits. Returning an empty string would be incorrect. The smallest positive integer whose digit product equals 1 is "1", so the implementation handles this case explicitly before any factorization begins.

Edge Case 2, Prime Factors Larger Than 7

Numbers such as 11, 13, or 44 contain prime factors that cannot appear in the factorization of any decimal digit. After extracting all possible factors from 9 through 2, a value greater than 1 remains. The implementation detects this condition and returns "-1".

Edge Case 3, Multiple Representations Exist

Many numbers can be represented in different ways. For example:

36 = 2 × 2 × 3 × 3
   = 4 × 9
   = 6 × 6

The smallest valid number is "49", not "66" and not "2233". The greedy extraction from large digits minimizes the digit count, and the final ascending ordering minimizes the numerical value among all representations with that digit count.

Edge Case 4, Large Powers of Two

Values such as 2^20 require many repeated divisions. A naive search would be infeasible. The greedy factorization repeatedly extracts 8s whenever possible, dramatically reducing the digit count. Because each division reduces the remaining value, the algorithm remains efficient even near the maximum input size.

Edge Case 5, Already a Single Digit

When n is any value from 2 through 9, the answer is simply the digit itself. The factorization loop extracts that digit directly, and after reversing a single-element list, the correct one-character string is returned.