<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:
    int nthUglyNumber(int n) {
        if (n <= 20) {
            // Faster path for smaller numbers.
            int index = 1;
            for (uint32_t i = 1;; ++i) {
                if (isUgly(i)) {
                    if (index == n)
                        return i;
                    ++index;
                }
            }
            return -1;
        }
        std::vector<uint32_t> ugly_nums;
        ugly_nums.reserve(2048);
        for (uint32_t i = 0; i < 31; ++i) {
            uint32_t three_power = 1 << i;
            for (uint32_t j = 0; j < 21; ++j) {
                uint32_t five_power = three_power;
                for (uint32_t k = 0; k < 14; ++k) {
                    ugly_nums.push_back(five_power);
                    const uint32_t next_five_power= five_power * 5u;
                    if (next_five_power / 5u != five_power)
                        break;
                    five_power = next_five_power;
                }
                const uint32_t next_three_power= three_power * 3u;
                if (next_three_power / 3u != three_power)
                    break;
                three_power = next_three_power;
            }
        }
        std::sort(ugly_nums.begin(), ugly_nums.end());
        return ugly_nums[n - 1];
    }
    bool isUgly(uint32_t n) {
        while (true) {
            if (n == 1)
                return true;
            if (n % 2 == 0)
                n /= 2;
            else if (n % 3 == 0)
                n /= 3;
            else if (n % 5 == 0)
                n /= 5;
            else
                return false;
        }
    }
};
15515