Ugly Number II
Write a program to find the n
-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5
.
Example:
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.
Note:
1
is typically treated as an ugly number.n
does not exceed 1690.
class Solution {
public int nthUglyNumber(int n) {
if (n <= 0)
return 0;
if (n == 1)
return 1;
int dp[] = new int[n];
// 1st ugly number is 1
dp[0] = 1;
int p2 = 0, p3 = 0, p5 = 0;
for (int i = 1; i < n; i++) {
int option1 = 2 * dp[p2];
int option2 = 3 * dp[p3];
int option3 = 5 * dp[p5];
dp[i] = Math.min(option1, Math.min(option2, option3));
if (dp[i] == option1)
p2++;
if (dp[i] == option2)
p3++;
if (dp[i] == option3)
p5++;
}
return dp[n - 1];
}
}
Last updated