# Find the smallest number whose digits multiply to a given number n

Given a number ‘n’, find the smallest number ‘p’ such that if we multiply all digits of ‘p’, we get ‘n’. The result ‘p’ should have minimum two digits.

Examples:

```Input:  n = 36
Output: p = 49
// Note that 4*9 = 36 and 49 is the smallest such number

Input:  n = 100
Output: p = 455
// Note that 4*5*5 = 100 and 455 is the smallest such number

Input: n = 1
Output:p = 11
// Note that 1*1 = 1

Input: n = 13
Output: Not Possible
```

For a given n, following are the two cases to be considered.
Case 1: n < 10 When n is smaller than n, the output is always n+10. For example for n = 7, output is 17. For n = 9, output is 19.

Case 2: n >= 10 Find all factors of n which are between 2 and 9 (both inclusive). The idea is to start searching from 9 so that the number of digits in result are minimized. For example 9 is preferred over 33 and 8 is preferred over 24.
Store all found factors in an array. The array would contain digits in non-increasing order, so finally print the array in reverse order.

Following is the implementation of above concept.

## C/C++

 `#include ` ` `  `// Maximum number of digits in output ` `#define MAX 50 ` ` `  `// prints the smallest number whose digits multiply to n ` `void` `findSmallest(``int` `n) ` `{ ` `    ``int` `i, j=0; ` `    ``int` `res[MAX]; ``// To sore digits of result in reverse order ` ` `  `    ``// Case 1: If number is smaller than 10 ` `    ``if` `(n < 10) ` `    ``{ ` `        ``printf``(``"%d"``, n+10); ` `        ``return``; ` `    ``} ` ` `  `    ``// Case 2: Start with 9 and try every possible digit ` `    ``for` `(i=9; i>1; i--) ` `    ``{ ` `        ``// If current digit divides n, then store all ` `        ``// occurrences of current digit in res ` `        ``while` `(n%i == 0) ` `        ``{ ` `            ``n = n/i; ` `            ``res[j] = i; ` `            ``j++; ` `        ``} ` `    ``} ` ` `  `    ``// If n could not be broken in form of digits (prime factors of n ` `    ``// are greater than 9) ` `    ``if` `(n > 10) ` `    ``{ ` `        ``printf``(``"Not possible"``); ` `        ``return``; ` `    ``} ` ` `  `    ``// Print the result array in reverse order ` `    ``for` `(i=j-1; i>=0; i--) ` `        ``printf``(``"%d"``, res[i]); ` `} ` ` `  `// Driver program to test above function ` `int` `main() ` `{ ` `    ``findSmallest(7); ` `    ``printf``(````" "````); ` ` `  `    ``findSmallest(36); ` `    ``printf``(````" "````); ` ` `  `    ``findSmallest(13); ` `    ``printf``(````" "````); ` ` `  `    ``findSmallest(100); ` `    ``return` `0; ` `} `

/div>

## Java

 `// Java program to find the smallest number whose  ` `// digits multiply to a given number n ` ` `  `import` `java.io.*; ` ` `  `class` `Smallest ` `{ ` `    ``// Function to prints the smallest number whose  ` `    ``// digits multiply to n ` `    ``static` `void` `findSmallest(``int` `n) ` `    ``{ ` `        ``int` `i, j=``0``; ` `        ``int` `MAX = ``50``; ` `        ``// To sore digits of result in reverse order ` `        ``int``[] res = ``new` `int``[MAX];  ` `  `  `        ``// Case 1: If number is smaller than 10 ` `        ``if` `(n < ``10``) ` `        ``{ ` `            ``System.out.println(n+``10``); ` `            ``return``; ` `        ``} ` `  `  `        ``// Case 2: Start with 9 and try every possible digit ` `        ``for` `(i=``9``; i>``1``; i--) ` `        ``{ ` `            ``// If current digit divides n, then store all ` `            ``// occurrences of current digit in res ` `            ``while` `(n%i == ``0``) ` `            ``{ ` `                ``n = n/i; ` `                ``res[j] = i; ` `                ``j++; ` `            ``} ` `        ``} ` `  `  `        ``// If n could not be broken in form of digits (prime factors of n ` `        ``// are greater than 9) ` `        ``if` `(n > ``10``) ` `        ``{ ` `            ``System.out.println(``"Not possible"``); ` `            ``return``; ` `        ``} ` `  `  `        ``// Print the result array in reverse order ` `        ``for` `(i=j-``1``; i>=``0``; i--) ` `            ``System.out.print(res[i]); ` `        ``System.out.println(); ` `    ``} ` `     `  `    ``// Driver program ` `    ``public` `static` `void` `main (String[] args)  ` `    ``{ ` `        ``findSmallest(``7``); ` `        ``findSmallest(``36``); ` `        ``findSmallest(``13``); ` `        ``findSmallest(``100``); ` `    ``} ` `} ` ` `  `// Contributed by Pramod Kumar `

## Python

 `# Python code to find the smallest number  ` `# whose digits multiply to give n ` ` `  `# function to print the smallest number whose  ` `# digits multiply to n ` `def` `findSmallest(n): ` `    ``# Case 1 - If the number is smaller than 10 ` `    ``if` `n < ``10``: ` `        ``print` `n``+``10` `        ``return` `     `  `    ``# Case 2 - Start with 9 and try every possible digit ` `    ``res ``=` `[] ``# to sort digits ` `    ``for` `i ``in` `range``(``9``,``1``,``-``1``): ` `        ``# If current digit divides n, then store all ` `        ``# occurences of current digit in res ` `        ``while` `n ``%` `i ``=``=` `0``: ` `            ``n ``=` `n ``/` `i ` `            ``res.append(i) ` `     `  `    ``# If n could not be broken in form of digits ` `    ``# prime factors of  n are greater than 9 ` `     `  `    ``if` `n > ``10``: ` `        ``print` `"Not Possible"` `        ``return` `         `  `    ``# Print the number from result array in reverse order ` `    ``n ``=` `res[``len``(res)``-``1``] ` `    ``for` `i ``in` `range``(``len``(res)``-``2``,``-``1``,``-``1``): ` `        ``n ``=` `10` `*` `n ``+` `res[i] ` `    ``print` `n ` `     `  `# Driver Code to test above function ` ` `  `findSmallest(``7``) ` ` `  `findSmallest(``36``) ` ` `  `findSmallest(``13``) ` ` `  `findSmallest(``100``) ` ` `  `# This code is contributed by Harshit Agrawal `

## C#

 `// C# program to find the smallest number whose  ` `// digits multiply to a given number n ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``// Function to prints the smallest number ` `    ``// whose digits multiply to n ` `    ``static` `void` `findSmallest(``int` `n) ` `    ``{ ` `         `  `        ``int` `i, j=0; ` `        ``int` `MAX = 50; ` `         `  `        ``// To sore digits of result in ` `        ``// reverse order ` `        ``int` `[]res = ``new` `int``[MAX];  ` ` `  `        ``// Case 1: If number is smaller than 10 ` `        ``if` `(n < 10) ` `        ``{ ` `            ``Console.WriteLine(n + 10); ` `            ``return``; ` `        ``} ` ` `  `        ``// Case 2: Start with 9 and try every ` `        ``// possible digit ` `        ``for` `(i = 9; i > 1; i--) ` `        ``{ ` `             `  `            ``// If current digit divides n, then ` `            ``// store all occurrences of current ` `            ``// digit in res ` `            ``while` `(n % i == 0) ` `            ``{ ` `                ``n = n / i; ` `                ``res[j] = i; ` `                ``j++; ` `            ``} ` `        ``} ` ` `  `        ``// If n could not be broken in form of ` `        ``// digits (prime factors of n ` `        ``// are greater than 9) ` `        ``if` `(n > 10) ` `        ``{ ` `            ``Console.WriteLine(``"Not possible"``); ` `            ``return``; ` `        ``} ` ` `  `        ``// Print the result array in reverse order ` `        ``for` `(i = j-1; i >= 0; i--) ` `            ``Console.Write(res[i]); ` `             `  `        ``Console.WriteLine(); ` `    ``} ` `     `  `    ``// Driver program ` `    ``public` `static` `void` `Main ()  ` `    ``{ ` `        ``findSmallest(7); ` `        ``findSmallest(36); ` `        ``findSmallest(13); ` `        ``findSmallest(100); ` `    ``} ` `} ` ` `  `// This code is contributed by nitin mittal. `

## PHP

 ` 1; ``\$i``--) ` `    ``{ ` `         `  `        ``// If current digit divides  ` `        ``// n, then store all ` `        ``// occurrences of current  ` `        ``// digit in res ` `        ``while` `(``\$n` `% ``\$i` `== 0) ` `        ``{ ` `            ``\$n` `= ``\$n` `/ ``\$i``; ` `            ``\$res``[``\$j``] = ``\$i``; ` `            ``\$j``++; ` `        ``} ` `    ``} ` ` `  `    ``// If n could not be broken  ` `    ``// in form of digits  ` `    ``// (prime factors of n ` `    ``// are greater than 9) ` `    ``if` `(``\$n` `> 10) ` `    ``{ ` `        ``echo` `"Not possible"``; ` `        ``return``; ` `    ``} ` ` `  `    ``// Print the result  ` `    ``// array in reverse order ` `    ``for` `(``\$i` `= ``\$j` `- 1; ``\$i` `>= 0; ``\$i``--) ` `        ``echo` `\$res``[``\$i``]; ` `} ` ` `  `    ``// Driver Code ` `    ``findSmallest(7); ` `    ``echo` ```" "````; ` ` `  `    ``findSmallest(36); ` `     `  `    ``echo` ```" "````; ` ` `  `    ``findSmallest(13); ` `    ``echo` ```" "````; ` ` `  `    ``findSmallest(100); ` ` `  `// This code is contributed by ajit ` `?> `

Output:

```17
49
Not possible
455 ```