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 C implementation of above concept.
[pastacode lang=”c” manual=”%23include%3Cstdio.h%3E%0A%20%0A%2F%2F%20Maximum%20number%20of%20digits%20in%20output%0A%23define%20MAX%2050%0A%20%0A%2F%2F%20prints%20the%20smallest%20number%20whose%20digits%20multiply%20to%20n%0Avoid%20findSmallest(int%20n)%0A%7B%0A%20%20%20%20int%20i%2C%20j%3D0%3B%0A%20%20%20%20int%20res%5BMAX%5D%3B%20%2F%2F%20To%20sore%20digits%20of%20result%20in%20reverse%20order%0A%20%0A%20%20%20%20%2F%2F%20Case%201%3A%20If%20number%20is%20smaller%20than%2010%0A%20%20%20%20if%20(n%20%3C%2010)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22%25d%22%2C%20n%2B10)%3B%0A%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Case%202%3A%20Start%20with%209%20and%20try%20every%20possible%20digit%0A%20%20%20%20for%20(i%3D9%3B%20i%3E1%3B%20i–)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20current%20digit%20divides%20n%2C%20then%20store%20all%0A%20%20%20%20%20%20%20%20%2F%2F%20occurrences%20of%20current%20digit%20in%20res%0A%20%20%20%20%20%20%20%20while%20(n%25i%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20n%20%3D%20n%2Fi%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20res%5Bj%5D%20%3D%20i%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20j%2B%2B%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20If%20n%20could%20not%20be%20broken%20in%20form%20of%20digits%20(prime%20factors%20of%20n%0A%20%20%20%20%2F%2F%20are%20greater%20than%209)%0A%20%20%20%20if%20(n%20%3E%2010)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22Not%20possible%22)%3B%0A%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Print%20the%20result%20array%20in%20reverse%20order%0A%20%20%20%20for%20(i%3Dj-1%3B%20i%3E%3D0%3B%20i–)%0A%20%20%20%20%20%20%20%20printf(%22%25d%22%2C%20res%5Bi%5D)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20findSmallest(7)%3B%0A%20%20%20%20printf(%22%5Cn%22)%3B%0A%20%0A%20%20%20%20findSmallest(36)%3B%0A%20%20%20%20printf(%22%5Cn%22)%3B%0A%20%0A%20%20%20%20findSmallest(13)%3B%0A%20%20%20%20printf(%22%5Cn%22)%3B%0A%20%0A%20%20%20%20findSmallest(100)%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”C Program” highlight=”” provider=”manual”/]Output:
17 49 Not possible 455[ad type=”banner”]