[leetcode] problem 264 – 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.

Note

1 is typically treated as an ugly number.

n does not exceed 1690.

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.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int (int n) {
int[] ugly = new int[n];
int t2 = 0;
int t3 = 0;
int t5 = 0;

ugly[0] = 1;

for (int i = 1; i < n; i++) {
ugly[i] = Math.min(2 * ugly[t2], Math.min(3 * ugly[t3], 5 * ugly[t5]));

if (ugly[i] == 2 * ugly[t2])
t2++;

if (ugly[i] == 3 * ugly[t3])
t3++;

if (ugly[i] == 5 * ugly[t5])
t5++;
}

return ugly[n-1];
}