264. Ugly Number II
Medium
An ugly number is a positive integer whose prime factors are limited to
2, 3, and 5.Given an integer
n, return the nth ugly number.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 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.
Constraints:
1 <= n <= 1690
Runtime: 0 ms, faster than 100%
Memory Usage: 4.2 MB, less than 48.33%
func nthUglyNumber(n int) int {
nums := make([]int, n)
nums[0] = 1
i2, i3, i5 := 0, 0, 0
for i:=1; i<n; i++ {
m := min(min(nums[i2]*2, nums[i3]*3), nums[i5]*5)
if m == nums[i2]*2 {
i2++
}
if m == nums[i3]*3 {
i3++
}
if m == nums[i5]*5 {
i5++
}
nums[i] = m
}
return nums[n - 1]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
Last modified 6mo ago