Smallest number whose digits multiplication is ‘N’
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.

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

Question

Smallest number whose digits multiplication is ‘N’

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.

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

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1).

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

Time Complexity: OtherExplanation:

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))’.

Accepted Answer

Greedy approach

The smallest value of ‘M’ must satisfy the following two conditions:

The number of digits in ‘M’ must be minimum. To achieve this, assign the maximum possible number of 9’s to ‘M’ (keep dividing ‘N’ by ‘9’ until it is no longer divisible). After that, do the same for 8’s and so on until ‘2’. This way, we assign the largest digit first, keeping the number of digits in ‘M’ to a minimum
Once the above condition is satisfied, the digits of ‘M’ must be in non-decreasing order for ‘M’ to be the smallest. We can do this by assigning the digits obtained above from right to left. Keep all the 9’s are at the rightmost, all the 8’s to their left, and so on. This way, the smallest digit becomes the most significant digit.

Example: ‘N’ = 64800

Initially ‘M = 0’, start to assign digits to ‘M’ from ‘9’ to ‘2’:

Assign ‘9’ to ‘M’ until ‘N’ is divisible by ‘9’:
- ‘M = 9’, update ‘N’,‘N = N/9 = 64800/9 = 7200’.
- ‘M = 99’, ‘N = 7200/9 = 800’.
Assign ‘8’ to ‘M’ until ‘N’ is divisible by ‘8’:
- ‘M = 899’,‘N = N/8 = 800/8 = 100’.
‘N = 100’ is not divisible by ‘7’, so move to the next digit.
‘N = 100’ is not divisible by ‘6’, so move to the next digit.
Assign ‘5’ to ‘M’ until ‘N’ is divisible by ‘5’:
- ‘M = 5899’,‘N = N/5 = 100/5 = 20’.
- ‘M = 55899’, ‘N = 20/5 = 4’.
Assign ‘4’ to ‘M’ until ‘N’ is divisible by ‘4’:
- ‘M = 455899’,‘N = N/4 = 4/4 = 1’.
‘N = 1’ is not divisible by ‘3’, so move to the next digit.
‘N = 1’ is not divisible by ‘2’.

After assigning the digits, we have ‘N = 1’, which means ‘N’ is equal to the multiplication of the digits in ‘M’. Thus, you should return ‘M = 55899’ as the answer.

Algorithm:

Set ‘RES = 0’. Use it to store the answer, i.e., the smallest ‘M’ value.
Set ‘P = 1’. Use it to store the place value of the digit to be added in ‘RES’. Initially, set ‘P’ to ‘1’ as the digits are added from the left, i.e., from the one’s place.
Run a loop where ‘i’ ranges from ‘9’ to ‘2’:
- Run a loop until ‘N’ is not equal to ‘0’:
  - ‘RES += P * i’. Insert the digit ‘i’ at place value ‘P’.
  - ‘P = P*10’. Update ‘P’ to store the next digit’s place value, i.e., to the previous digit’s right.
  - ‘N /= i’. Update ‘N’.
- If ‘RES > INT32_MAX’, then ‘M’ cannot fit in a 32-bit signed integer:
  - Return ‘0’ as the answer.
If ‘N’ is not equal to ‘1’, then ‘N’ cannot be factorized using integers from ‘2’ to ‘9’:
- Return ‘0’ as the answer.
Return ‘RES’ as the answer. This is the smallest ‘M’ value.

Space Complexity: O(1)Explanation:

O(1).

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

Time Complexity: O(logn)Explanation:

O(log(N)), where ‘N’ is the given number.

The worst-case scenario will arise when ‘M’ contains only the digit ‘2’, taking ‘log(N)’ iterations to compute ‘M’. Thus, the time complexity is ‘log(N)’.

Python (3.5)

'''

    Time Complexity : O(log(N))

    Space Complexity : O(1)



    where 'N' is the given integer.

'''



def smallestDigitMuliply(n):



    # To store the answer.

    res = 0

    # Stores the place value of the digit to be added.

    p = 1



    # Add the digits from '9' to '2' in decreasing order.

    for i in range(9, 1, -1):



        # Add all the possible 'i' digits into 'res'.

        while (n % i == 0):



            # Insert the digit 'i' at place value 'p'.

            res += p * i

            # Update 'p' to store the place value of next digit.

            p *= 10

            # Update 'n'.

            n //= i



            # Check if 'res' exceeds '32-bit' integer value.

            if (res > 2147483647):



                # 'INT32_MAX = 2,147,483,647', out of int range.

                return 0



    # 'n' cannot be factorized.

    if (n != 1):

        return 0



    return res

Java (SE 1.8)

/*
    Time Complexity : O(log(N))
    Space Complexity : O(1)

    where 'N' is the given integer.
*/

import java.util.ArrayList;

public class Solution {
    public static int smallestDigitMuliply(int n) {
        // To store the answer.
        long res = 0;
        // Stores the place value of the digit to be added.
        long p = 1;

        // Add the digits from '9' to '2' in decreasing order.
        for (int i = 9; i >= 2; i--) {
            // Add all the possible 'i' digits into 'res'.
            while (n % i == 0) {
                // Insert the digit 'i' at place value 'p'.
                res += p * i;
                // Update 'p' to store the place value of next digit.
                p *= 10;
                // Update 'n'.
                n /= i;

                // 'Integer.MAX_VALUE = 2,147,483,647' (largest value in a '32-bit' signed integer).
                if (res > Integer.MAX_VALUE) {
                    return 0;
                }
            }
        }

        // 'n' cannot be factorized.
        if (n != 1) {
            return 0;
        }
        
        return (int)res;
    }
}

C++ (g++ 5.4)

/*
    Time Complexity : O(log(N))
    Space Complexity : O(1)

    where 'N' is the given integer.
*/

int smallestDigitMuliply(int n) {
    // To store the answer.
    long res = 0;
    // Stores the place value of the digit to be added.
    long p = 1;

    // Add the digits from '9' to '2' in decreasing order.
    for (int i = 9; i >= 2; i--) {
        // Add all the possible 'i' digits into 'res'.
        while (n % i == 0) {
            // Insert the digit 'i' at place value 'p'.
            res += p * i;
            // Update 'p' to store the place value of next digit.
            p *= 10;
            // Update 'n'.
            n /= i;

            // 'INT32_MAX = 2,147,483,647' (largest value in a '32-bit' signed integer).
            if (res > INT32_MAX) {
                return 0;
            }
        }
    }

    // 'n' cannot be factorized.
    if (n != 1) {
        return 0;
    }

    return res;
}

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:

Input format:

Output format:

Note:

Constraints:

Top TCS Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in TCS Software Developer