264. Ugly Number II

Problem

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.

Solution

/**
 * @param {number} n
 * @return {number}
 */
var nthUglyNumber = function(n) {
  if (n < 1) return 0;

  var dp = [1];
  var t2 = 0;
  var t3 = 0;
  var t5 = 0;

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

  return dp[n - 1];
};

class Solution {
    public int nthUglyNumber(int n) {
        int[] ugly = new int[n];
        int i2 = 0;
        int i3 = 0;
        int i5 = 0;
        int ugly2 = 2;
        int ugly3 = 3;
        int ugly5 = 5;
        int nextugly;
        ugly[0] = 1;
        for (int i = 1; i < n; i++) {
            nextugly = Math.min(Math.min(ugly2, ugly3), ugly5);
            ugly[i] = nextugly;
            if (nextugly == ugly2) {
                i2++;
                ugly2 = ugly[i2] * 2;
            }
            if (nextugly == ugly3) {
                i3++;
                ugly3 = ugly[i3] * 3;
            }
            if (nextugly == ugly5) {
                i5++;
                ugly5 = ugly[i5] * 5;
            }
        }
        return ugly[n - 1];
    }
}

Explain:

1. 除了 1，其它结果都是以前的结果乘 2, 3, 5 得来的；
2. dp[i] = min(dp[t2] * 2, dp[t3] * 3, dp[t5] * 5)，t2, t3, t5 是上一次乘 2, 3, 5 的时候；

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).