[LeetCode] Problem 264 - Ugly Number II

Posted on | In ,

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 nthUglyNumber(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];
}