Three Short Solutions in Python 3 (Bisect, Heap, DP)
1) Using Bisect: (5 lines)\n\nclass Solution:\n    def nthUglyNumber(self, n: int) -> int:\n    \tN, I = [1], {2:0, 3:0, 5:0}\n    \tfor _ in range(n-1):\n    \
_1) Using Bisect: (5 lines)_\n```\nclass Solution:\n    def nthUglyNumber(self, n: int) -> int:\n    \tN, I = [1], {2:0, 3:0, 5:0}\n    \tfor _ in range(n-1):\n    \t\tI = {i:bisect.bisect(N, N[-1]//i, I[i]) for i in [2,3,5]}\n    \t\tN.append(min(N[I[2]]*2,N[I[3]]*3,N[I[5]]*5))\n    \treturn N[-1]\n\n\n```\n_2) Using Heap: (6 lines)_\n```\nclass Solution:\n    def nthUglyNumber(self, n: int) -> int:\n    \tN, m, S = [1], 1, set()\n    \tfor _ in range(n):\n    \t\twhile m in S: m = heapq.heappop(N)\n    \t\tS.add(m)\n    \t\tfor i in [2,3,5]: heapq.heappush(N,i*m)\n    \treturn m\n\n\n```\n_3) Using DP: (5 lines)_\n```\nclass Solution:\n    def nthUglyNumber(self, n: int) -> int:\n    \tN, p, I = [1], [2,3,5], [0]*3\n    \tfor _ in range(n-1):\n    \t\tN.append(min([N[I[i]]*p[i] for i in range(3)]))\n    \t\tfor i in range(3): I[i] += N[I[i]]*p[i] == N[-1]\n    \treturn N[-1]\n\t\t\n\t\t\n\t\t\n- Junaid Mansuri\n(LeetCode ID)@hotmail.com
['Dynamic Programming', 'Heap (Priority Queue)', 'Python', 'Python3']