[Python] O(n) universal dp solution, explained
Let us solve this problem for general case: that is not only for 2,3,5 divisors, but for any of them and any number of them. factors = [2,3,5] and  k=3 in our c
Let us solve this problem for general case: that is not only for `2,3,5` divisors, but for any of them and any number of them. `factors = [2,3,5]` and  `k=3` in our case.\nLet `Numbers` be an array, where we keep all our **ugly** numbers. Also, note, that any ugly number is some other ugly number, multiplied by `2`, `3` or `5`. So, let `starts` be the indexes of ugly numbers, that when multiplied by `2`, `3` or `5` respectively, produces the smallest ugly number that is larger than the current overall maximum ugly number.. Let us do several first steps to understand it better:\n\n1. `starts = [0,0,0]` for numbers `2,3,5`, so `new_num = min(1*2,1*3,1*5) = 2`, and now `starts = [1,0,0]`, `Numbers = [1,2]`.\n2. `starts = [1,0,0]`, so `new_num = min(2*2,1*3,1*5) = 3`, and now `starts = [1,1,0]`, `Numbers = [1,2,3]`.\n3. `starts = [1,1,0]`, so `new_num = min(2*2,2*3,1*5) = 4`, so now `starts = [2,1,0]`, `Numbers = [1,2,3,4]`.\n4. `starts = [2,1,0]`, so `new_num = min(3*2,2*3,1*5) = 5`, so now `starts = [2,1,1]`, `Numbers = [1,2,3,4,5]`.\n5. `starts = [2,1,1]`, so `new_num = min(3*2,2*3,2*5) = 6`, so let us be carefull in this case: we need to increase two numbers from `start`, because our new number `6` can be divided both by `2` and `3`, so now `starts = [3,2,1]`, `Numbers = [1,2,3,4,5,6]`.\n6. `starts = [3,2,1]`, so `new_num = min(4*2,3*3,2*5) = 8`, so now `starts = [4,2,1]`, `Numbers = [1,2,3,4,5,6,8]`\n7. `starts = [4,2,1]`, so `new_num = min(5*2,3*3,2*5) = 9`, so now `starts = [4,3,1]`, `Numbers = [1,2,3,4,5,6,8,9]`.\n8. `starts = [4,3,1]`, so `new_num = min(5*2,4*3,2*5) = 10`, so we need to update two elements from `starts` and now `starts = [5,3,2]`, `Numbers = [1,2,3,4,5,6,8,9,10]`\n9. `starts = [5,3,2]`, so `new_num = min(6*2,4*3,3*5) = 12`, we again need to update two elements from `starts`, and now `starts = [6,4,2]`, `Numbers = [1,2,3,4,5,6,8,9,10,12]`.\n10. `starts = [6,4,2]`, so `new_num = min(8*2,5*3,3*5) = 15`, we again need to update two elements from `starts`, and now `starts = [6,5,3]`, `Numbers = [1,2,3,4,5,6,8,9,10,12,15]`.\n\n**Complexity**: time complexity is `O(n)` to find ugly number with number `n`, because on each step we check `3` possible candidates. Space complexity is `O(n)` as well. Note, that it can be easily generalized for different amount of divisors with time complexity `O(nk)`, where `k` is total number of divisors.\n\n```\nclass Solution:\n    def nthUglyNumber(self, n):\n        factors, k = [2,3,5], 3\n        starts, Numbers = [0] * k, [1]\n        for i in range(n-1):\n            candidates = [factors[i]*Numbers[starts[i]] for i in range(k)]\n            new_num = min(candidates)\n            Numbers.append(new_num)\n            starts = [starts[i] + (candidates[i] == new_num) for i in range(k)]\n        return Numbers[-1]\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Dynamic Programming']