{"id":26704,"date":"2017-12-22T20:51:53","date_gmt":"2017-12-22T15:21:53","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26704"},"modified":"2017-12-22T20:51:53","modified_gmt":"2017-12-22T15:21:53","slug":"c-programming-ugly-numbers","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-ugly-numbers\/","title":{"rendered":"C Programming &#8211; Ugly Numbers"},"content":{"rendered":"<p>Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, \u2026 shows the first 11 ugly numbers. By convention, 1 is included.<\/p>\n<p>Given a number n, the task is to find n\u2019th Ugly number.<\/p>\n<pre>Input  : n = 7\r\nOutput : 8\r\n\r\nInput  : n = 10\r\nOutput : 12\r\n\r\nInput  : n = 15\r\nOutput : 24\r\n\r\nInput  : n = 150\r\nOutput : 5832<\/pre>\n<p><center><strong>Method 1 (Simple)<\/strong><\/center><br \/>\nLoop for all positive integers until ugly number count is smaller than n, if an integer is ugly than increment ugly number count.<\/p>\n<p>To check if a number is ugly, divide the number by greatest divisible powers of 2, 3 and 5, if the number becomes 1 then it is an ugly number otherwise not.<\/p>\n<p>For example, let us see how to check for 300 is ugly or not. Greatest divisible power of 2 is 4, after dividing 300 by 4 we get 75. Greatest divisible power of 3 is 3, after dividing 75 by 3 we get 25. Greatest divisible power of 5 is 25, after dividing 25 by 25 we get 1. Since we get 1 finally, 300 is ugly number.<\/p>\n[ad type=&#8221;banner&#8221;]\n<p><strong>Implementation:<\/strong><\/p>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">C<\/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\/># include&lt;stdlib.h&gt;<br\/> <br\/>\/*This function divides a by greatest divisible <br\/>  power of b*\/<br\/>int maxDivide(int a, int b)<br\/>{<br\/>  while (a%b == 0)<br\/>   a = a\/b; <br\/>  return a;<br\/>}   <br\/> <br\/>\/* Function to check if a number is ugly or not *\/<br\/>int isUgly(int no)<br\/>{<br\/>  no = maxDivide(no, 2);<br\/>  no = maxDivide(no, 3);<br\/>  no = maxDivide(no, 5);<br\/>   <br\/>  return (no == 1)? 1 : 0;<br\/>}    <br\/> <br\/>\/* Function to get the nth ugly number*\/<br\/>int getNthUglyNo(int n)<br\/>{<br\/>  int i = 1; <br\/>  int count = 1;   \/* ugly number count *\/<br\/> <br\/>  \/*Check for all integers untill ugly count <br\/>    becomes n*\/<br\/>  while (n &gt; count)<br\/>  {<br\/>    i++;      <br\/>    if (isUgly(i))<br\/>      count++; <br\/>  }<br\/>  return i;<br\/>}<br\/> <br\/>\/* Driver program to test above functions *\/<br\/>int main()<br\/>{<br\/>    unsigned no = getNthUglyNo(150);<br\/>    printf(&quot;150th ugly no. is %d &quot;,  no);<br\/>    getchar();<br\/>    return 0;<br\/>}<\/code><\/pre> <\/div>\n<p>Output:<\/p>\n<pre>150th ugly no. is 5832<\/pre>\n<p>This method is not time efficient as it checks for all integers until ugly number count becomes n, but space complexity of this method is O(1)<\/p>\n<p><center><strong>Method 2 (Use Dynamic Programming)<\/strong><\/center><br \/>\nHere is a time efficient solution with O(n) extra space. The ugly-number sequence is 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, \u2026<br \/>\nbecause every number can only be divided by 2, 3, 5, one way to look at the sequence is to split the sequence to three groups as below:<br \/>\n(1) 1\u00d72, 2\u00d72, 3\u00d72, 4\u00d72, 5\u00d72, \u2026<br \/>\n(2) 1\u00d73, 2\u00d73, 3\u00d73, 4\u00d73, 5\u00d73, \u2026<br \/>\n(3) 1\u00d75, 2\u00d75, 3\u00d75, 4\u00d75, 5\u00d75, \u2026<\/p>\n[ad type=&#8221;banner&#8221;]\n<p>We can find that every subsequence is the ugly-sequence itself (1, 2, 3, 4, 5, \u2026) multiply 2, 3, 5. Then we use similar merge method as merge sort, to get every ugly number from the three subsequence. Every step we choose the smallest one, and move one step after.<\/p>\n<pre>1 Declare an array for ugly numbers:  ugly[n]\r\n2 Initialize first ugly no:  ugly[0] = 1\r\n3 Initialize three array index variables i2, i3, i5 to point to \r\n   1st element of the ugly array: \r\n        i2 = i3 = i5 =0; \r\n4 Initialize 3 choices for the next ugly no:\r\n         next_mulitple_of_2 = ugly[i2]*2;\r\n         next_mulitple_of_3 = ugly[i3]*3\r\n         next_mulitple_of_5 = ugly[i5]*5;\r\n5 Now go in a loop to fill all ugly numbers till 150:\r\nFor (i = 1; i &lt; 150; i++ ) \r\n{\r\n    \/* These small steps are not optimized for good \r\n      readability. Will optimize them in C program *\/\r\n    next_ugly_no  = Min(next_mulitple_of_2,\r\n                        next_mulitple_of_3,\r\n                        next_mulitple_of_5); \r\n    if (next_ugly_no  == next_mulitple_of_2) \r\n    {             \r\n        i2 = i2 + 1;        \r\n        next_mulitple_of_2 = ugly[i2]*2;\r\n    } \r\n    if (next_ugly_no  == next_mulitple_of_3) \r\n    {             \r\n        i3 = i3 + 1;        \r\n        next_mulitple_of_3 = ugly[i3]*3;\r\n     }            \r\n     if (next_ugly_no  == next_mulitple_of_5)\r\n     {    \r\n        i5 = i5 + 1;        \r\n        next_mulitple_of_5 = ugly[i5]*5;\r\n     } \r\n     ugly[i] =  next_ugly_no       \r\n}\/* end of for loop *\/ \r\n6.return next_ugly_no\r\n<\/pre>\n[ad type=&#8221;banner&#8221;]\n<p><strong>Example:<\/strong><br \/>\nLet us see how it works<\/p>\n<pre>initialize\r\n   ugly[] =  | 1 |\r\n   i2 =  i3 = i5 = 0;\r\n\r\nFirst iteration\r\n   ugly[1] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)\r\n            = Min(2, 3, 5)\r\n            = 2\r\n   ugly[] =  | 1 | 2 |\r\n   i2 = 1,  i3 = i5 = 0  (i2 got incremented ) \r\n\r\nSecond iteration\r\n    ugly[2] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)\r\n             = Min(4, 3, 5)\r\n             = 3\r\n    ugly[] =  | 1 | 2 | 3 |\r\n    i2 = 1,  i3 =  1, i5 = 0  (i3 got incremented ) \r\n\r\nThird iteration\r\n    ugly[3] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)\r\n             = Min(4, 6, 5)\r\n             = 4\r\n    ugly[] =  | 1 | 2 | 3 |  4 |\r\n    i2 = 2,  i3 =  1, i5 = 0  (i2 got incremented )\r\n\r\nFourth iteration\r\n    ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)\r\n              = Min(6, 6, 5)\r\n              = 5\r\n    ugly[] =  | 1 | 2 | 3 |  4 | 5 |\r\n    i2 = 2,  i3 =  1, i5 = 1  (i5 got incremented )\r\n\r\nFifth iteration\r\n    ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)\r\n              = Min(6, 6, 10)\r\n              = 6\r\n    ugly[] =  | 1 | 2 | 3 |  4 | 5 | 6 |\r\n    i2 = 3,  i3 =  2, i5 = 1  (i2 and i3 got incremented )\r\n\r\nWill continue same way till I &lt; 150<\/pre>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">C<\/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;bits\/stdc++.h&gt;<br\/>using namespace std;<br\/> <br\/>\/* Function to get the nth ugly number*\/<br\/>unsigned getNthUglyNo(unsigned n)<br\/>{<br\/>    unsigned ugly[n]; \/\/ To store ugly numbers<br\/>    unsigned i2 = 0, i3 = 0, i5 = 0;<br\/>    unsigned next_multiple_of_2 = 2;<br\/>    unsigned next_multiple_of_3 = 3;<br\/>    unsigned next_multiple_of_5 = 5;<br\/>    unsigned next_ugly_no = 1;<br\/> <br\/>    ugly[0] = 1;<br\/>    for (int i=1; i&lt;n; i++)<br\/>    {<br\/>       next_ugly_no = min(next_multiple_of_2,<br\/>                           min(next_multiple_of_3,<br\/>                               next_multiple_of_5));<br\/>       ugly[i] = next_ugly_no;<br\/>       if (next_ugly_no == next_multiple_of_2)<br\/>       {<br\/>           i2 = i2+1;<br\/>           next_multiple_of_2 = ugly[i2]*2;<br\/>       }<br\/>       if (next_ugly_no == next_multiple_of_3)<br\/>       {<br\/>           i3 = i3+1;<br\/>           next_multiple_of_3 = ugly[i3]*3;<br\/>       }<br\/>       if (next_ugly_no == next_multiple_of_5)<br\/>       {<br\/>           i5 = i5+1;<br\/>           next_multiple_of_5 = ugly[i5]*5;<br\/>       }<br\/>    } \/*End of for loop (i=1; i&lt;n; i++) *\/<br\/>    return next_ugly_no;<br\/>}<br\/> <br\/>\/* Driver program to test above functions *\/<br\/>int main()<br\/>{<br\/>    int n = 150;<br\/>    cout &lt;&lt; getNthUglyNo(n);<br\/>    return 0;<br\/>}<\/code><\/pre> <\/div>\n<p>Output :<\/p>\n<pre>5832\r\n<\/pre>\n<p><strong>Algorithmic Paradigm: <\/strong>Dynamic Programming<br \/>\n<strong>Time Complexity: <\/strong>O(n)<br \/>\n<strong>Auxiliary Space: <\/strong>O(n)<\/p>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>C Programming &#8211; Ugly Numbers &#8211; Dynamic Programming Ugly numbers are numbers whose only prime factors are 2, 3 or 5. Every step we choose the smallest one<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69866,1,70145],"tags":[79791,79788,79799,79789,72839,79793,79784,79800,79794,72852,72855,79783,72853,79782,79787,72851],"class_list":["post-26704","post","type-post","status-publish","format-standard","hentry","category-c-programming","category-coding","category-dynamic-programming","tag-greatest-divisible-power","tag-hamming","tag-hamming-number-program-in-c","tag-hamming-numbers-algorithm","tag-how-to-solve-dynamic-programming-problems","tag-missing-number","tag-nth-ugly-number","tag-number-formation-in-c","tag-prime-factor","tag-problems-on-dynamic-programming","tag-simple-dynamic-programming-example","tag-super-ugly-number","tag-types-of-dynamic-programming","tag-ugly-numbers","tag-write-a-function-to-find-the-n","tag-youtube-dynamic-programming"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26704","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\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26704"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26704\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26704"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26704"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26704"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}