Smallest Number with Given Digit Product

Given a positive integer 'N', find and return the smallest number 'M', such that the product of all the digits in 'M' is equal to 'N'. If such an 'M' is not possible or if 'M' cannot fit in a 32-bit signed integer, return 0.

Example:

Input:

N = 90

Output:

259

Explanation:

For 'N' = 90, the possible values for 'M' include 259 (2*5*9 = 90), 3352 (3*3*5*2 = 90), 2335 (2*3*3*5 = 90), and 952 (9*5*2 = 90), among others. The smallest possible 'M' is 259, hence, the answer is 259.

Constraints:

1

Question

Smallest Number with Given Digit Product

Given a positive integer 'N', find and return the smallest number 'M', such that the product of all the digits in 'M' is equal to 'N'. If such an 'M' is not possible or if 'M' cannot fit in a 32-bit signed integer, return 0.

Example:

Input:

N = 90

Output:

Explanation:

For 'N' = 90, the possible values for 'M' include 259 (2*5*9 = 90), 3352 (3*3*5*2 = 90), 2335 (2*3*3*5 = 90), and 952 (9*5*2 = 90), among others. The smallest possible 'M' is 259, hence, the answer is 259.

Constraints:

1 <= T <= 1000
1 <= N <= 10⁹
Time limit: 1 sec

Accepted Answer

Find the smallest number with given digit product equal to a positive integer N.

Iterate from 2 to 9 and find the smallest digit that divides N, then add it to the result.
Repeat the process until N is reduced to 1 or a prime number.
If N cannot be reduced to 1 or a prime number, return 0.

Asked in TCS