Smallest number whose digits multiplication is ‘N’

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.

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.