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
Given a number n, the task is to find n\u2019th Ugly number.<\/p>\n
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<\/center>\u00a0<\/p>\n Method (Use Dynamic Programming)<\/strong><\/center>
\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
\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:
\n(1) 1\u00d72, 2\u00d72, 3\u00d72, 4\u00d72, 5\u00d72, \u2026
\n(2) 1\u00d73, 2\u00d73, 3\u00d73, 4\u00d73, 5\u00d73, \u2026
\n(3) 1\u00d75, 2\u00d75, 3\u00d75, 4\u00d75, 5\u00d75, \u2026<\/p>\n[ad type=\u201dbanner\u201d]\nWe 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
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 < 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=\u201dbanner\u201d]\nExample:<\/strong>
\nLet us see how it works<\/p>\ninitialize\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 < 150<\/pre>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Python%20program%20to%20find%20n\u2019th%20Ugly%20number%0A%20%0A%23%20Function%20to%20get%20the%20nth%20ugly%20number%0Adef%20getNthUglyNo(n)%3A%0A%20%0A%20%20%20%20ugly%20%3D%20%5B0%5D%20*%20n%20%23%20To%20store%20ugly%20numbers%0A%20%0A%20%20%20%20%23%201%20is%20the%20first%20ugly%20number%0A%20%20%20%20ugly%5B0%5D%20%3D%201%0A%20%0A%20%20%20%20%23%20i2%2C%20i3%2C%20i5%20will%20indicate%20indices%20for%202%2C3%2C5%20respectively%0A%20%20%20%20i2%20%3D%20i3%20%3Di5%20%3D%200%0A%20%0A%20%20%20%20%23%20set%20initial%20multiple%20value%0A%20%20%20%20next_multiple_of_2%20%3D%202%0A%20%20%20%20next_multiple_of_3%20%3D%203%0A%20%20%20%20next_multiple_of_5%20%3D%205%0A%20%0A%20%20%20%20%23%20start%20loop%20to%20find%20value%20from%20ugly%5B1%5D%20to%20ugly%5Bn%5D%0A%20%20%20%20for%20l%20in%20range(1%2C%20n)%3A%0A%20%0A%20%20%20%20%20%20%20%20%23%20choose%20the%20min%20value%20of%20all%20available%20multiples%0A%20%20%20%20%20%20%20%20ugly%5Bl%5D%20%3D%20min(next_multiple_of_2%2C%20next_multiple_of_3%2C%20next_multiple_of_5)%0A%20%0A%20%20%20%20%20%20%20%20%23%20increment%20the%20value%20of%20index%20accordingly%0A%20%20%20%20%20%20%20%20if%20ugly%5Bl%5D%20%3D%3D%20next_multiple_of_2%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20i2%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20next_multiple_of_2%20%3D%20ugly%5Bi2%5D%20*%202%0A%20%0A%20%20%20%20%20%20%20%20if%20ugly%5Bl%5D%20%3D%3D%20next_multiple_of_3%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20i3%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20next_multiple_of_3%20%3D%20ugly%5Bi3%5D%20*%203%0A%20%0A%20%20%20%20%20%20%20%20if%20ugly%5Bl%5D%20%3D%3D%20next_multiple_of_5%3A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20i5%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20next_multiple_of_5%20%3D%20ugly%5Bi5%5D%20*%205%0A%20%0A%20%20%20%20%23%20return%20ugly%5Bn%5D%20value%0A%20%20%20%20return%20ugly%5B-1%5D%0A%20%0Adef%20main()%3A%0A%20%0A%20%20%20%20n%20%3D%20150%0A%20%0A%20%20%20%20print%20getNthUglyNo(n)%0A%20%0A%20%0Aif%20__name__%20%3D%3D%20\u2019__main__\u2019%3A%0A%20%20%20%20main()%0A%20\u2033 message=\u201dPython\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\nOutput :<\/p>\n
5832\r\n<\/pre>\nAlgorithmic Paradigm: <\/strong>Dynamic Programming
\nTime Complexity: <\/strong>O(n)
\nAuxiliary Space: <\/strong>O(n)<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"Python Programming – Ugly Numbers – Dynamic Programming Ugly numbers are numbers whose only prime factors are 2, 3 or 5.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,70145,4148],"tags":[72847,72842,72845,70483,72848,72840,72846,72994,79785,72843,72992,72854,72844,72850,79786,79791,79788,79790,79789,72839,79793,79784,79792,79794,72852,72855,79783,72853,79782,79787,72851],"class_list":["post-26733","post","type-post","status-publish","format-standard","hentry","category-coding","category-dynamic-programming","category-python","tag-concept-of-dynamic-programming","tag-define-dynamic-programming","tag-definition-of-dynamic-programming","tag-dynamic-programming","tag-dynamic-programming-code-generation-algorithm","tag-dynamic-programming-definition","tag-dynamic-programming-in-data-structure","tag-dynamic-programming-in-python","tag-dynamic-programming-in-python-based-on-ugly-number","tag-dynamic-programming-problems","tag-dynamic-programming-python","tag-dynamic-programming-set-1","tag-dynamic-programming-software","tag-explain-dynamic-programming","tag-find-nth-ugly-number","tag-greatest-divisible-power","tag-hamming","tag-hamming-number-program-in-python","tag-hamming-numbers-algorithm","tag-how-to-solve-dynamic-programming-problems","tag-missing-number","tag-nth-ugly-number","tag-number-formation-in-python","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\/26733","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=26733"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26733\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26733"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26733"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26733"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}