Short and O(n), Python and C++
I love this problem. Came up with a linear time solution almost 13 years ago and now I still correctly remembered that it was problem 136 at the now defunct acm
I love this problem. Came up with a linear time solution almost 13 years ago and now I still correctly remembered that it was problem 136 at the now defunct acm.uva.es :-)\n\n---\n\n**Python** ... **Simple Precompute** ... 64 ms\n\nIt's fastest to precompute and store all possibilities for lookup, and it's simplest to just generate them out of order and then sort them.\n\n    class Solution:\n        ugly = sorted(2**a * 3**b * 5**c\n                      for a in range(32) for b in range(20) for c in range(14))\n        def nthUglyNumber(self, n):\n            return self.ugly[n-1]\n\n---\n\n**Python** ... **O(n), generate first n in order** ... 308 ms\n\nMy version of [epsilon0's solution](https://uva.onlinejudge.org/board/viewtopic.php?p=6441#p6441). It's nicer than my own old one.\n\nThis generates the first n ugly numbers, in order from smallest to largest, in O(n) time. For each prime 2, 3 and 5, have an index to the next number that can be multiplied with the prime to produce a new ugly number. Update the three indexes and then add the smallest of the three candidate ugly numbers.\n\n    def nthUglyNumber(self, n):\n        ugly = [1]\n        i2 = i3 = i5 = 0\n        while len(ugly) < n:\n            while ugly[i2] * 2 <= ugly[-1]: i2 += 1\n            while ugly[i3] * 3 <= ugly[-1]: i3 += 1\n            while ugly[i5] * 5 <= ugly[-1]: i5 += 1\n            ugly.append(min(ugly[i2] * 2, ugly[i3] * 3, ugly[i5] * 5))\n        return ugly[-1]\n\n---\n\n**Python** ... **O(n), generate first n in order with heapq.merge** ... 416 ms\n\nI like using heapq.merge.\n\n    def nthUglyNumber(self, n):\n        q2, q3, q5 = [2], [3], [5]\n        ugly = 1\n        for u in heapq.merge(q2, q3, q5):\n            if n == 1:\n                return ugly\n            if u > ugly:\n                ugly = u\n                n -= 1\n                q2 += 2 * u,\n                q3 += 3 * u,\n                q5 += 5 * u,\n\nWorks, but might not be totally safe, both because I extend lists while iterating over them and because at the start, q2 becomes empty for a moment, which I think allows heapq.merge to drop it (at least in CPython it just doesn't, as it first yields the value before trying to get the next one from that list, and when it continues, the list isn't empty anymore).\n\n---\n\n**C++** ... **O(n), generate first n in order** ... 12 ms\n\nC++ version of the second Python solution, though adding extra variables for the three candidates to prevent re-multiplication.\n\n    int nthUglyNumber(int n) {\n        vector<int> ugly(n, 1);\n        int c2 = 2, c3 = 3, c5 = 5;\n        int i2 = 0, i3 = 0, i5 = 0;\n        for (int i=1; i<n; ++i) {\n            int last = ugly[i] = min(c2, min(c3, c5));\n            while (c2 <= last) c2 = 2 * ugly[++i2];\n            while (c3 <= last) c3 = 3 * ugly[++i3];\n            while (c5 <= last) c5 = 5 * ugly[++i5];\n        }\n        return ugly[n-1];\n    }\n\n---\n\n**C++** ... **O(n), generate on demand and remember** ... 4 ms\n\nSame as the previous, but I keep everything in static variables and only compute more when needed. It's faster, and I think pretty neat.\n\n    int nthUglyNumber(int n) {\n        static vector<int> ugly {1};\n        static int last(1);\n        static int c2(2), c3(3), c5(5);\n        static int i2(0), i3(0), i5(0);\n        while (ugly.size() < n) {\n            while (c2 <= last) c2 = 2 * ugly[++i2];\n            while (c3 <= last) c3 = 3 * ugly[++i3];\n            while (c5 <= last) c5 = 5 * ugly[++i5];\n            ugly.push_back(last = min(c2, min(c3, c5)));\n        }\n        return ugly[n-1];\n    }\n\n---\n\n**C++** ... **Simple Precompute** ... 4 ms\n\nPrecompute all possibilities in easy order and sort them.\n\n    int nthUglyNumber(int n) {\n        static vector<int> ugly;\n        long long a, b, c, m = INT_MAX;\n        if (ugly.empty()) {\n            for (a=1; a<=m; a*=2)\n                for (b=a; b<=m; b*=3)\n                    for (c=b; c<=m; c*=5)\n                        ugly.push_back(c);\n            sort(begin(ugly), end(ugly));\n        }\n        return ugly[n-1];\n    }\n\n---\n\n**My own old one**\n\nPython version of my own O(n) C++ solution from almost [13 years ago](https://uva.onlinejudge.org/board/viewtopic.php?p=6444#p6444). Good old times...\nMaybe I'll try to improve it, but mainly I wanted to see how a pretty much direct translation would look.\n\n    def nthUglyNumber(self, n):\n        factor = 2, 3, 5\n        lists = [collections.deque([1]) for _ in range(3)]\n        for _ in range(n - 1):\n            next = [lists[i][0] * factor[i] for i in range(3)]\n            winner = min(range(3), key=lambda j: next[j])\n            for i in range(winner, 3):\n                lists[i] += next[winner],\n            lists[winner].popleft()\n        return lists[2][-1]
['Python', 'C++']