Last Updated: 12 Nov, 2021
Digit Product
Moderate
Asked in company
Ninja’s friend challenged him with an interesting problem to test his intelligence. His friend gives him the number ‘N’, Ninja’s task is to find the smallest number ‘X’ such that the product of the digits of ‘X’ is equal to ‘N’.Can you help Ninja to solve this problem?
You are given a number ‘N’, you have to find the minimum number ‘X’ such that the product of the digits of ‘X’ is equal to ‘N’.If no such number is found, print -1.
For Example
If the given number is 36, the smallest number will be 49 as the product of digits is 36 (=4*9).
Input Format:
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains two integers, ‘N’ denoting the given number.
Output Format:
For each test case, print an integer corresponding to the minimum number ‘X’ such that the product of the digits of ‘X’ is equal to ‘N’.
Print the output of each test case in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^6.
Time limit: 1 sec
Approaches
In this approach, we will find the factors of ‘N’ as, we know the digits can be between 1 to 9, so if we found a prime factor greater than 9, the answer is not possible. After assuring that the answer is possible, we will try every number from 1 and check its digit product using the function HELPER(X) which will return the product of digits of ‘X’.So, we will return the minimum ‘X’ for which HELPER(X) is equal to ‘N’.
Algorithm:
- Define ‘HELPER(X)’ function that will return the product of digits of ‘X’:
- Set ‘ANS’ as 1.
- While ‘X’>0:
- Set ‘DIGIT’ as ‘X’%10.
- Set ‘X’ as ‘X’/10.
- Set ‘ANS’ as ‘ANS’ * ’DIGIT’.
- Return ‘ANS’.
- Check for any prime factor of ‘N’ greater than 9.
- Set ‘TEMP’ as ‘N’.
- For i in range 2 to 9, do the following:
- While ‘TEMP’ is divisible by i:
- Set ‘TEMP’ as ‘TEMP’/i.
- While ‘TEMP’ is divisible by i:
- If ‘TEMP’ >9:
- A prime factor greater than 9 is found, so the answer is not possible.
- Return -1.
- Set ‘ANS’ as 1.
- While(TRUE):
- Set ‘PROD’ as ‘HELPER(‘ANS’).
- If ‘PROD’ is equal to ‘N’, do the following:
- Return ‘ANS’.
- Set ‘ANS’ as ‘ANS’ +1.
In this approach, we will find the factors of ‘N’ and use them to generate the required number. We know the digits can be between 1 to 9, so if we found a factor greater than 9, the answer is not possible. So, we will store the factors in the array in decreasing order, and with his factors array, we will generate the number in the reverse order of the factors as we need to find the smallest number.
Algorithm:
- Declare an array ‘FACTORS’ to store the factors.
- For i in range 9 to 2, do the following:
- While ‘N’ is divisible by i:
- Set ‘N’ as ‘N’/i.
- Insert i into the ‘FACTORS’ list.
- While ‘N’ is divisible by i:
- If N >9:
- One factor is greater than 9, so the answer is not possible.
- Return -1.
- Declare ‘ANS’ to store the required number.
- For i in range (size of ‘FACTORS’ -1) to 0, do the following:
- Set ‘ANS’ as ‘ANS’ * 10.
- Set ‘ANS’as ‘ANS’ + 'FACTORS'[i].
- Return ‘ANS’.