Smallest number whose digits multiplication is ‘N’

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
9 upvotes
Asked in companies
OlaHewlett Packard EnterpriseCogoport

Problem statement

You are given a positive integer ‘N’. The task is to find and return the smallest number, ‘M’, such that the multiplication of all the digits in ‘M’ is equal to ‘N’. If no such ‘M’ is possible or ‘M’ cannot fit in a 32-bit signed integer, return 0.

Example: 
‘N’ = 90

Possible values for ‘M’ are:
1. 259 (2*5*9 = 90) 
2. 3352 (3*3*5*2 = 90) 
3. 2335 (2*3*3*5 = 90) 
4. 952 (9*5*2 = 90), and so on.
Here, ‘259’ is the smallest possible ‘M’. Thus, you should return ‘259’ as the answer.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.

The first and only line of each test case contains an integer ‘N’, i.e., the given integer.
Output format: 
For every test case, return the smallest possible ‘M’ value. If no such ‘M’ is possible or ‘M’ cannot fit in a 32-bit signed integer, return 0.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 1000
1 <= N <= 10^9

Time limit: 1 sec

Sample input 1:

2
120
62

Sample output 1:

358
0

Explanation of sample input 1:

Test Case 1:

Possible values for ‘M’ are:
1. 358 (3*5*8 = 120)
2. 2345 (2*3*4*5 = 120)
3. 22235 (2*2*2*3*5 = 120), and so on.
Here, ‘358’ is the smallest possible ‘M’. Thus, you should return ‘358’ as the answer.

Test Case 2:

The factorization of ‘62 = 2*31’. As ‘31’ is a prime number, it cannot have single-digit factors (‘0’ to ‘9’) . Thus, it’s impossible to have an integer ‘M’, such that the multiplication of its digits is equal to ‘62’. You should return ‘0’ as the answer.

Sample input 2:

2
168
180

Sample output 2:

378
459
Hint

Check for all possible ‘M’ values.

Approaches (2)
Brute force

A simple approach will be to iterate through all possible ‘M’ values, i.e., from ‘1’ to ‘2147483647’ (the largest value that a signed 32-bit integer field can hold), and check if their digit multiplication is equal to ‘N’.

 

Algorithm:

  • Run a loop where ‘i’ ranges from ‘1’ to ‘2147483647’:
    • Set ‘CUR = i’. The current ‘M’ value.
    • Set ‘MUL = 1’. Use it to store the digit multiplication of ‘M’.
    • Run a loop until ‘cur’ is not equal to ‘0’ to find the digit multiplication of ‘CUR’:
      • ‘MUL = MUL*(CUR/10)’. Multiply the digit at one’s place in ‘CUR’ to ‘MUL’.
      • ‘CUR /= 10’. Divide ‘CUR’ by ‘10’ to move the next digit in ‘CUR’ to one’s place.
    • If ‘MUL’ is equal to ‘N’, then ‘i’ is the smallest ‘M’ value possible:
      • Return ‘i’ as the answer.
  • Return ‘0’ as we could not find a valid ‘M’ value.
Time Complexity

O(M*log(M)), where ‘M’ is the answer.

 

We iterate through all the integers up to ‘M’ or ‘2147483647’ (when ‘N’ has a prime factor greater than ‘9’), and in each iteration, we compute the digit multiplication of the current ‘M’ in ‘O(log(M))’. Thus, the time complexity is ‘O(M*log(M))’.

Space Complexity

O(1).

 

Since we are not using any extra space, space complexity is constant.

Code Solution
(100% EXP penalty)
Smallest number whose digits multiplication is ‘N’
Full screen
Console