{"id":26175,"date":"2017-10-26T20:18:33","date_gmt":"2017-10-26T14:48:33","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26175"},"modified":"2017-10-26T20:18:33","modified_gmt":"2017-10-26T14:48:33","slug":"c-programming-find-smallest-number-whose-digits-multiply-given-number-n","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-find-smallest-number-whose-digits-multiply-given-number-n\/","title":{"rendered":"C Programming &#8211; Find the smallest number whose digits multiply to a given number n"},"content":{"rendered":"<p>Given a number \u2018n\u2019, find the smallest number \u2018p\u2019 such that if we multiply all digits of \u2018p\u2019, we get \u2018n\u2019. The result \u2018p\u2019 should have minimum two digits.<span id=\"more-129576\"><\/span><\/p>\n<p>Examples:<\/p>\n<pre>Input:  n = 36\r\nOutput: p = 49 \r\n\/\/ Note that 4*9 = 36 and 49 is the smallest such number\r\n\r\nInput:  n = 100\r\nOutput: p = 455\r\n\/\/ Note that 4*5*5 = 100 and 455 is the smallest such number\r\n\r\nInput: n = 1\r\nOutput:p = 11\r\n\/\/ Note that 1*1 = 1\r\n\r\nInput: n = 13\r\nOutput: Not Possible\r\n<\/pre>\n<p>For a given n, following are the two cases to be considered.<br \/>\n<strong>Case 1: n &lt; 10<\/strong> 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.<\/p>\n<p><strong>Case 2: n &gt;= 10<\/strong> 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.<br \/>\nStore all found factors in an array. The array would contain digits in non-increasing order, so finally print the array in reverse order.<\/p>\n[ad type=&#8221;banner&#8221;]\n<p>Following is C implementation of above concept.<\/p>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">C Program<\/span> <\/div> <pre class=\"language-c code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-c code-embed-code\">#include&lt;stdio.h&gt;<br\/> <br\/>\/\/ Maximum number of digits in output<br\/>#define MAX 50<br\/> <br\/>\/\/ prints the smallest number whose digits multiply to n<br\/>void findSmallest(int n)<br\/>{<br\/>    int i, j=0;<br\/>    int res[MAX]; \/\/ To sore digits of result in reverse order<br\/> <br\/>    \/\/ Case 1: If number is smaller than 10<br\/>    if (n &lt; 10)<br\/>    {<br\/>        printf(&quot;%d&quot;, n+10);<br\/>        return;<br\/>    }<br\/> <br\/>    \/\/ Case 2: Start with 9 and try every possible digit<br\/>    for (i=9; i&gt;1; i--)<br\/>    {<br\/>        \/\/ If current digit divides n, then store all<br\/>        \/\/ occurrences of current digit in res<br\/>        while (n%i == 0)<br\/>        {<br\/>            n = n\/i;<br\/>            res[j] = i;<br\/>            j++;<br\/>        }<br\/>    }<br\/> <br\/>    \/\/ If n could not be broken in form of digits (prime factors of n<br\/>    \/\/ are greater than 9)<br\/>    if (n &gt; 10)<br\/>    {<br\/>        printf(&quot;Not possible&quot;);<br\/>        return;<br\/>    }<br\/> <br\/>    \/\/ Print the result array in reverse order<br\/>    for (i=j-1; i&gt;=0; i--)<br\/>        printf(&quot;%d&quot;, res[i]);<br\/>}<br\/> <br\/>\/\/ Driver program to test above function<br\/>int main()<br\/>{<br\/>    findSmallest(7);<br\/>    printf(&quot;\\n&quot;);<br\/> <br\/>    findSmallest(36);<br\/>    printf(&quot;\\n&quot;);<br\/> <br\/>    findSmallest(13);<br\/>    printf(&quot;\\n&quot;);<br\/> <br\/>    findSmallest(100);<br\/>    return 0;<br\/>}<\/code><\/pre> <\/div>\n<p>Output:<\/p>\n<pre>17\r\n49\r\nNot possible\r\n455<\/pre>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>C Programming Find the smallest number whose digits multiply to a given number n &#8211; Mathematical Algorithms &#8211; Given a number \u2018n\u2019 find the smallest number \u2018p\u2019<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,69866,1,74058],"tags":[75580,77622,77609,76322,77621,74075,77612,77372,77618,75205,75572,75578,77611,77610,77382,77606,77607,77616,77388,75652,77603,75298,76265,77620,77608,74064,77604,77605,76317,76619,76316,77614,77617,70565,75577,75299,76620,75583,75660,75519,74093,76318,76315,74059,76323,75581,77613,75569,77619,77615],"class_list":["post-26175","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming","category-coding","category-mathematical-algorithms","tag-1-is-prime-number-or-not","tag-10-digit-prime-number","tag-5-prime-numbers","tag-all-prime-numbers","tag-common-number","tag-composite-numbers-from-1-to-1000","tag-different-kinds-of-numbers","tag-digits-math","tag-explain-prime-numbers","tag-finding-prime-numbers","tag-first-4-prime-numbers","tag-first-five-prime-numbers","tag-first-in-math","tag-first-three-prime-numbers","tag-greatest-6-digit-number","tag-greatest-four-digit-number","tag-how-many-4-digit-numbers-are-there","tag-how-many-6-digit-numbers-are-there-in-all","tag-largest-3-digit-prime-number","tag-largest-4-digit-number","tag-largest-prime-number","tag-list-of-prime-numbers","tag-math-numbers","tag-natural-numbers-examples","tag-natural-numbers-list","tag-numbers-divisible-by-7","tag-one-two-three-numbers","tag-prime","tag-prime-factors-of-a-number","tag-prime-no","tag-prime-nos","tag-prime-number-chart","tag-prime-number-table","tag-prime-numbers","tag-prime-numbers-from-1-to-20","tag-prime-numbers-list","tag-prime-numbers-up-to-100","tag-smallest-2-digit-number","tag-smallest-8-digit-number","tag-smallest-composite-number","tag-smallest-even-number","tag-smallest-natural-number","tag-smallest-prime-number","tag-smallest-three-digit-number","tag-the-prime-numbers","tag-three-digit-prime-numbers","tag-what-is-the-number","tag-what-is-the-prime-factorization-of-50","tag-what-is-the-smallest-4-digit-number","tag-what-r-prime-numbers"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26175","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26175"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26175\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26175"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26175"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26175"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}