1
// Ugly number II
2
// https://leetcode.com/problems/ugly-number-ii/
3

4
class Solution {
5
  public int nthUglyNumber(int n) {
6
    int[] dp = new int[n];
7
    dp[0] = 1;
8
    int i2 = 0, i3 = 0, i5 = 0;
9
    for (int i = 1; i < n; i++) {
10
      dp[i] = Math.min(dp[i2] * 2, Math.min(dp[i3] * 3, dp[i5] * 5));
11
      if (dp[i] == dp[i2] * 2) i2++;
12
      if (dp[i] == dp[i3] * 3) i3++;
13
      if (dp[i] == dp[i5] * 5) i5++;
14
    }
15
    return dp[n - 1];
16
  }
17
}