Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. 

Example:


Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:  


       1 is typically treated as an ugly number.
       n does not exceed 1690.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Data structures

Mathematics

Starter code: class Solution:
    def nthUglyNumber(self, n: int) -> int:
        

Solutions:
class Solution:
	res = [1]
	idx = [0, 0, 0]

	def nthUglyNumber(self, n):
		if n <= 0:
			return None
		(idx2, idx3, idx5) = Solution.idx
		while len(Solution.res) < n:
			Solution.res.append(min(Solution.res[idx2] * 2, Solution.res[idx3] * 3, Solution.res[idx5] * 5))
			while idx2 < len(Solution.res) and Solution.res[idx2] * 2 <= Solution.res[-1]:
				idx2 += 1
			while idx3 < len(Solution.res) and Solution.res[idx3] * 3 <= Solution.res[-1]:
				idx3 += 1
			while idx5 < len(Solution.res) and Solution.res[idx5] * 5 <= Solution.res[-1]:
				idx5 += 1
		Solution.idx = [idx2, idx3, idx5]
		return Solution.res[n - 1]


class Solution:
	ugly = sorted((2 ** a * 3 ** b * 5 ** c for a in range(32) for b in range(20) for c in range(14)))

	def nthUglyNumber(self, n):
		return self.ugly[n - 1]