{"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 < 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 >= 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=\u201dbanner\u201d]\n<p>Following is C implementation of above concept.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%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\u2013)%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\u2013)%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\u201d message=\u201dC Program\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Output:<\/p>\n<pre>17\r\n49\r\nNot possible\r\n455<\/pre>\n[ad type=\u201dbanner\u201d]\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}]}}