Digit Product

Moderate
0/80
Average time to solve is 25m
12 upvotes
Asked in company
Amazon

Problem statement

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).
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
36
42
Sample Output 1:
49
67
Explanation of sample input 1:
For the first test case,

The smallest number is 36 as the product of 4 and 9 is 36.
Hence, the answer is 49.


For the second test case:

The smallest number is 67 as the product of 4 and 9 is  42.
Hence, the answer is 67.
Sample Input 2:
2
10
21
Sample Output 2:
25
37
Hint

Try all numbers till be smallest number is found.

Approaches (2)
Brute Force

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.
  • 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.
Time Complexity

O(MAX_ANS * log10(MAX_ANS)), where ‘MAX_ANS’ is the greatest answer possible.


In this approach, we are trying each number till the answer is not found, and for each try, we are traversing its all digits, which takes O(log10X) time. So, in the worst case, the total time is MAX_ANS * log10(MAX_ANS). Hence, the overall time complexity is O(MAX_ANS * log10(MAX_ANS)).

Space Complexity

O(1)

 

In this approach, we are using constant space. Hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Digit Product
Full screen
Console