Skip to main content
Talentd

Smallest Number With Given Digit Product - Solution & Explanation

MediumPremiumFree on FleetCodeMathGreedy8 min readAsked at: Microsoft
Practice this problem

Problem Statement

Given a positive integer n, return a string representing the smallest positive integer such that the product of its digits is equal to n, or "-1" if no such number exists.

 

Example 1:

Input: n = 105
Output: "357"
Explanation: 3 * 5 * 7 = 105. It can be shown that 357 is the smallest number with a product of digits equal to 105. So the answer would be "357".

Example 2:

Input: n = 7
Output: "7"
Explanation: Since 7 has only one digit, its product of digits would be 7. We will show that 7 is the smallest number with a product of digits equal to 7. Since the product of numbers 1 to 6 is 1 to 6 respectively, so "7" would be the answer.

Example 3:

Input: n = 44
Output: "-1"
Explanation: It can be shown that there is no number such that its product of digits is equal to 44. So the answer would be "-1".

 

Constraints:

  • 1 <= n <= 1018

Approach Overview

Problem Overview: Given an integer n, build the smallest possible number whose digits multiply to exactly n. Each digit must be between 1 and 9. If no such number exists, return -1. The challenge is minimizing the resulting number while preserving the required digit product.

Approach 1: Brute Force Enumeration (Exponential Time)

Generate candidate numbers and check whether the product of their digits equals n. You compute the digit product by iterating through each digit and multiplying them. The smallest valid candidate is returned. This approach is impractical because the search space grows exponentially with the number of digits. Time complexity is O(10^k) where k is the digit length explored, and space complexity is O(1) aside from candidate generation.

Approach 2: Prime Factorization + Greedy (Optimal, O(log n))

Digits 2–9 are composite representations of prime factors 2, 3, 5, 7. Instead of searching numbers, factorize n using the largest possible digit values from 9 down to 2. For each digit d, repeatedly divide n while n % d == 0 and record d in the result. This greedy step compresses multiple prime factors into a single digit (for example, 8 = 2×2×2, 9 = 3×3), reducing the total number of digits and therefore the final number size.

After extracting all factors, check if n became 1. If not, the product requires a prime factor larger than 7, which cannot be represented by a single digit, so the answer is -1. Otherwise, sort the collected digits in ascending order and concatenate them. Sorting ensures the smallest possible numeric value. The factorization loop runs at most log n times, giving O(log n) time complexity and O(log n) space for storing digits.

This strategy combines math reasoning with a greedy choice. The key observation: larger digits compress factors more efficiently, while sorting at the end guarantees the smallest number.

Recommended for interviews: The greedy factorization approach is the expected solution. It shows you recognize the relationship between digits and prime factors and know how to compress factors optimally. Mentioning brute force first demonstrates problem exploration, but implementing the greedy method proves algorithmic maturity and strong mathematical reasoning.

Solution

We consider prime factorizing the number n. If there are prime factors greater than 9 in n, then it is impossible to find a number that meets the conditions, because prime factors greater than 9 cannot be obtained by multiplying numbers from 1 to 9. For example, 11 cannot be obtained by multiplying numbers from 1 to 9. Therefore, we only need to consider whether there are prime factors greater than 9 in n. If there are, return -1 directly.

Otherwise, if the prime factors include 7 and 5, then the number n can first be decomposed into several 7s and 5s. Two 3s can be combined into a 9, three 2s can be combined into an 8, and a 2 and a 3 can be combined into a 6. Therefore, we only need to decompose the number into numbers from 2 to 9. We can use a greedy method, preferentially decomposing into 9, then decomposing into 8, and so on.

The time complexity is O(log n), and the space complexity is O(1).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(10^k)O(1)Conceptual baseline to understand the problem; not practical for real constraints
Prime Factorization + GreedyO(log n)O(log n)General and optimal solution; preferred in interviews and competitive programming

Video Solution

Day 629 - Teaching Kids Programming - Smallest Number With Given Digit Product (Greedy Factorization • Doctor Lai • 49 views views

Frequently Asked Questions

Is Smallest Number With Given Digit Product easy or hard?
The problem is typically classified as Medium. The coding portion is short, but recognizing the greedy factorization insight requires understanding how digits represent combinations of prime factors.
Smallest Number With Given Digit Product Python/Java solution
Implement a loop from digit 9 down to 2 and repeatedly divide n when divisible. Append the digit to a result list each time. If n becomes 1, sort the digits and join them into a string. This implementation is straightforward in Python, Java, C++, and Go with identical logic.
How to solve Smallest Number With Given Digit Product in O(log n)?
Iterate digits from 9 down to 2 and repeatedly divide n while it is divisible by that digit. Store each successful divisor. If the remaining value becomes 1, sort the collected digits in ascending order and concatenate them to form the smallest number. If a leftover factor greater than 1 remains, no valid number exists.
What is the best approach for Smallest Number With Given Digit Product?
The optimal approach uses greedy prime factorization. Repeatedly divide n by digits from 9 down to 2 and store those digits. This compresses prime factors into the fewest digits, which minimizes the resulting number after sorting. The algorithm runs in O(log n) time with O(log n) space for storing digits.
Is Smallest Number With Given Digit Product asked at Google/Amazon/Meta?
Problems involving digit factorization and greedy decomposition appear in interviews at large companies such as Google, Amazon, and Meta. While this exact problem may vary in wording, the underlying concept of compressing prime factors into digits is a common algorithmic pattern.
What data structure is used in Smallest Number With Given Digit Product?
The solution mainly relies on mathematical factorization and a simple list or array to store digits. After collecting the digits, sorting the list ensures the final number is lexicographically smallest. No complex data structures are required.
What is the time complexity of Smallest Number With Given Digit Product?
The greedy factorization solution runs in O(log n) time because each division reduces n multiplicatively. At most log n factor operations occur. Space complexity is O(log n) for storing the digits that form the resulting number.

Ready to solve this problem?

Practice Smallest Number With Given Digit Product with our built-in code editor and test cases.

Practice on FleetCode
Previous

Smallest Divisible Digit Product I

Next

Smallest Divisible Digit Product II