264. Ugly Number II

Problem

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

Problem Summary

Given an integer n, find and return the nth ugly number. An ugly number is a positive integer whose prime factors only include 2, 3, and/or 5.

Solution Ideas

• Solution one, method for generating ugly numbers: first use the smallest prime factor 1 and multiply it by 2, 3, and 5 respectively; the resulting numbers are ugly numbers. Continuously multiply these numbers by 2, 3, and 5 respectively, remove duplicates, then sort them in ascending order; the nth number is the answer. Sorting can be implemented with a min-heap, and deduplication can be done with a map. Time complexity O(n log n), space complexity O(n).
• The above solution spends time on sorting. The root cause of needing sorting is that a smaller ugly number multiplied by 5 can be greater than a larger ugly number multiplied by 2. How to ensure that after each multiplication, the ugly numbers found are ordered is the key to removing sorting and improving time complexity. It is easy to understand with an example: initially the set of ugly numbers only contains {1}. After multiplying by 2, 3, and 5, store the smallest result in the set {1,2}. In the next round of multiplication, since 1 was already multiplied by 2 in the previous round, do not multiply 1 by 2 again in this round, so multiply 1 by 3 and 5. Multiply 2 by 2, 3, and 5. Store the smallest result in the set {1,2,3}. Continuing with this strategy, the ugly number selected in each round is ordered and non-repeating. The concrete implementation can be done with 3 pointers and an array. Time complexity O(n), space complexity O(n).

Code

package leetcode

func nthUglyNumber(n int) int {
	dp, p2, p3, p5 := make([]int, n+1), 1, 1, 1
	dp[0], dp[1] = 0, 1
	for i := 2; i <= n; i++ {
		x2, x3, x5 := dp[p2]*2, dp[p3]*3, dp[p5]*5
		dp[i] = min(min(x2, x3), x5)
		if dp[i] == x2 {
			p2++
		}
		if dp[i] == x3 {
			p3++
		}
		if dp[i] == x5 {
			p5++
		}
	}
	return dp[n]
}

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