264. Ugly Number II

1. Description

Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

2. Example

Example 1:
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.

3. Note

• 1 is typically treated as an ugly number.
• n does not exceed 1690.

4. Solutions

My Accepted Solution

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

It is obvious that we could judge every number to find whether it is a ugly number, until we get the nth ugly number.
But we could also solve the problem using dp.
uglyNumber[i] means i-th ugly number
dp = uglyNumber
$ dp[i] = \begin{cases} 1, & \text{i == 1} \\
min(dp[last 2’s multiple index]*2, min(dp[last 3’s multiple index]*3, dp[last 5’s multiple index]*5)) , & \text{i > 1} \\
\end{cases} $

class Solution 
{
public:
    int nthUglyNumber(int n) 
    {
        vector<int> uglyNumber(n, 1);
        int multipleIndex2 = 0, multipleIndex3 = 0, multipleIndex5 = 0;
        for(int i = 1; i < n; i++)
        {
            int new2Multiple = uglyNumber[multipleIndex2] * 2;
            int new3Multiple = uglyNumber[multipleIndex3] * 3;
            int new5Multiple = uglyNumber[multipleIndex5] * 5;

            uglyNumber[i] = min(new2Multiple, min(new3Multiple, new5Multiple));

            if(uglyNumber[i] == new2Multiple) multipleIndex2++;
            if(uglyNumber[i] == new3Multiple) multipleIndex3++;
            if(uglyNumber[i] == new5Multiple) multipleIndex5++;
        }

        return uglyNumber.back();
    }
};