> For the complete documentation index, see [llms.txt](https://txfs19260817.gitbook.io/leetcode-go-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://txfs19260817.gitbook.io/leetcode-go-notes/solutions/264.-ugly-number-ii.md).

# 264. Ugly Number II

## LeetCode [264. Ugly Number II](https://github.com/txfs19260817/LeetCode-Go/blob/master/solutions/title/README.md)

### Description

Given an integer `n`, return *the* `nth` ***ugly number***.

**Ugly number** is a positive number whose prime factors only include `2`, `3`, and/or `5`.

**Example 1:**

```
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.
```

**Example 2:**

```
Input: n = 1
Output: 1
Explanation: 1 is typically treated as an ugly number.
```

**Constraints:**

* `1 <= n <= 1690`

### Tags

Math, Dynamic Programming, Heap

### Solution

We define an array dp. Each `dp[i]` represents the ith ugly number. The edge case is `dp[1]=1`, which is the smallest ugly number. Then, we initialize 3 pointers `p2, p3, p5` starting from 1. The transferring function is `dp[i] = min(dp[p2]*2, dp[p3]*3, dp[p5]*5)`. After updating, we compare `dp[i]` with each of the three. The pointer of the one which is equal to `dp[i]` will be moving one step forward. Finally, we return the result `dp[n]`.

### Complexity

* Time complexity: $$O(n)$$
* Space complexity: $$O(n)$$

### Code

```go
func nthUglyNumber(n int) int {
	dp := make([]int, n+1)
	dp[1] = 1
	p2, p3, p5 := 1, 1, 1
	for i := 2; i <= n; i++ {
		n2, n3, n5 := dp[p2]*2, dp[p3]*3, dp[p5]*5
		dp[i] = min(n2, min(n3, n5))
		if dp[i] == n2 {
			p2++
		}
		if dp[i] == n3 {
			p3++
		}
		if dp[i] == n5 {
			p5++
		}
	}
	return dp[n]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
```

## Reference

1. [丑数 II](https://leetcode-cn.com/problems/ugly-number-ii/solution/chou-shu-ii-by-leetcode-solution-uoqd/)
2. [三指针方法的理解方式](https://leetcode-cn.com/problems/ugly-number-ii/solution/san-zhi-zhen-fang-fa-de-li-jie-fang-shi-by-zzxn/)