Smallest Number With Given Digit Product

Smallest Number With Given Digit Product

What is this problem about?

The "Smallest Number With Given Digit Product" interview question asks you to find the smallest positive integer whose digits, when multiplied together, equal a given value n. For example, if n = 12, the smallest number is 26 because 2 * 6 = 12. While 34 or 43 also have a product of 12, 26 is the smallest. This "Smallest Number With Given Digit Product coding problem" requires working backwards from the product to the digits.

Why is this asked in interviews?

Microsoft and other top companies ask this to evaluate a candidate's greedy algorithmic thinking and basic number theory. It tests if you can recognize that to keep the number "smallest," you should use as few digits as possible (which means using larger digits like 8 and 9) and arrange them in increasing order. It also tests your ability to handle cases where no such number exists (e.g., if n has a prime factor greater than 7).

Algorithmic pattern used

This problem follows the "Math and Greedy interview pattern".

1. If n < 10, the smallest number is simply n.
2. For n >= 10, try to divide n by the largest possible single-digit divisors starting from 9 down to 2.
3. Every time n is divisible by a digit d, add d to a list and update n = n / d.
4. If after checking all digits n is still greater than 1, it means n had a prime factor like 11, 13, etc. No such number exists; return -1.
5. Otherwise, sort the collected digits in non-decreasing order to form the smallest number.

Example explanation

Let n = 36.

1. Try 9: 36 % 9 == 0. Digits: [9]. n = 4.
2. Try 9, 8, 7, 6, 5: No.
3. Try 4: 4 % 4 == 0. Digits: [9, 4]. n = 1.
4. Stop. Sorted digits: [4, 9]. Result: 49. (Note: 66 also works, but 49 is smaller).

Common mistakes candidates make

A common error is trying to find the digits using a smaller-to-larger approach (like 2, 3...). This results in more digits (e.g., for 12, it might give 223 instead of 26), making the number much larger. Another mistake is forgetting to handle the case where n cannot be factorized into single digits. Some candidates also struggle with n=0 or n=1, which are important edge cases.

Interview preparation tip

In "smallest number" problems involving digits, "Greedy" usually means "maximize the value of the trailing digits to minimize the total number of digits." This "Smallest Number With Given Digit Product interview question" perfectly illustrates the power of greedy factorization.