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.

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
     res=[1]
     idx=[0,0,0]
     def nthUglyNumber(self, n):
         """
         :type n: int
         :rtype: int
         """
         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]

class Solution:
     res=[1]
     idx=[0,0,0]
     def nthUglyNumber(self, n):
         """
         :type n: int
         :rtype: int
         """
         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]