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

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).