<p>An <strong>ugly number</strong> is a positive integer whose prime factors are limited to <code>2</code>, <code>3</code>, and <code>5</code>.</p>

<p>Given an integer <code>n</code>, return <em>the</em> <code>n<sup>th</sup></code> <em><strong>ugly number</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 10
<strong>Output:</strong> 12
<strong>Explanation:</strong> [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 1
<strong>Explanation:</strong> 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 1690</code></li>
</ul>

class Solution {
public:
    
    long long cache[50][50][50] = {0};
    
    int nthUglyNumber(int n) {
        vector<int> ugly_numbers = {1};
        
        int i=0, j=0, k=0;
        
        int x = 2123366400;
        
        while (x%2 == 0) {
            i++;
            x/=2;
        }
        x = 2123366400;
        while (x%3 == 0) {
            j++;
            x/=3;
        }
        x = 2123366400;
        while (x%5 == 0) {
            k++;
            x/=5;
        }
        
        cache[0][0][0] = 1;
        x = 0;
        
        for (int a=0; a<50; a++) {
            for (int b=0; b<50; b++) {
                for (int c=0; c<50; c++) {
                    
                    if (a+b+c == 0) {
                        continue;
                    }
                    
                    // cout<<"a: "<<a<<" | b: "<<b<<" | c: "<<c<<"\n";
                    
                    if (a != 0 && cache[a-1][b][c] != 0 && cache[a-1][b][c] * 2 <= 2123366400) {
                        cache[a][b][c] = cache[a-1][b][c] * 2;
                    }
                    else if (b != 0 && cache[a][b-1][c] != 0 && cache[a][b-1][c] * 3 <= 2123366400) {
                        cache[a][b][c] = cache[a][b-1][c] * 3;
                    }
                    else if (c != 0 && cache[a][b][c-1] != 0 && cache[a][b][c-1] * 5 <= 2123366400) {
                        cache[a][b][c] = cache[a][b][c-1] * 5;
                    }
                    else {
                        continue;
                    }
                    
                    if (cache[a][b][c] <= 2123366400) {
                        x++;
                        ugly_numbers.push_back(cache[a][b][c]);
                    }
                }
            }
        }
        
        sort(ugly_numbers.begin(), ugly_numbers.end());
        
        // cout<<"x: "<<x<<"\n";
        
        return ugly_numbers[n-1];
    }
};
24065