Write a program to find the`n`

-th ugly number. Ugly numbers arepositive numberswhose prime factors only include`2, 3, 5`

.Example:Input:n = 10Output:12Explanation:`1, 2, 3, 4, 5, 6, 8, 9, 10, 12`

is the sequence of the first`10`

ugly numbers.Note:1.`1`

is typically treated as an ugly number. 2.`n`

does not exceed 1690.

Well, the most straightforward approach would be generating all ugly numbers by keeping multiplying powers of `2,3,5`

, and sorting them. Notably, there are 1690 ugly numbers smaller than 2^{31}-1, hence we could use that as the upper bound. More details are shown as blow credit to @StefanPochmann:

```
class Solution:
# 32, 20, 14 are chosen to meet num<2^31-1
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]
```

#### Dynamic programming

A better approach is to utilize dynamic programming. As shown below – the red numbers are part of the ugly numbers sequence – the sequence of ugly numbers is generated by keeping multiplying `2,3,5`

. Therefore we can maintain three-pointers with each pointing to one of `2,3,5`

. And we have:

```
next_num = min{arr[p2]*2,
arr[p3]*3,
arr[p5]*5}
```

```
class Solution:
def nthUglyNumber(self, n: int) -> int:
# three pointers to 2,3,5
i2=i3=i5=0
q = [1]
while len(q) < n:
a,b,c = q[i2]*2, q[i3]*3, q[i5]*5
cur = min(a,b,c)
if cur == a:
i2 += 1
if cur == b:
i3 += 1
if cur == c:
i5 += 1
q.append(cur)
return q[-1]
```