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=”banner”]\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=”banner”]\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 Python<\/span> <\/div> # Python program to find n'th Ugly number # Function to get the nth ugly numberdef getNthUglyNo(n): ugly = [0] * n # To store ugly numbers # 1 is the first ugly number ugly[0] = 1 # i2, i3, i5 will indicate indices for 2,3,5 respectively i2 = i3 =i5 = 0 # set initial multiple value next_multiple_of_2 = 2 next_multiple_of_3 = 3 next_multiple_of_5 = 5 # start loop to find value from ugly[1] to ugly[n] for l in range(1, n): # choose the min value of all available multiples ugly[l] = min(next_multiple_of_2, next_multiple_of_3, next_multiple_of_5) # increment the value of index accordingly if ugly[l] == next_multiple_of_2: i2 += 1 next_multiple_of_2 = ugly[i2] * 2 if ugly[l] == next_multiple_of_3: i3 += 1 next_multiple_of_3 = ugly[i3] * 3 if ugly[l] == next_multiple_of_5: i5 += 1 next_multiple_of_5 = ugly[i5] * 5 # return ugly[n] value return ugly[-1] def main(): n = 150 print getNthUglyNo(n) if __name__ == '__main__': main() <\/code><\/pre> <\/div>\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=”banner”]\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}]}}