264. Ugly Number II

LeetCode 264. Ugly Number II

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

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

2. 三指针方法的理解方式