<p>A <strong>super ugly number</strong> is a positive integer whose prime factors are in the array <code>primes</code>.</p>

<p>Given an integer <code>n</code> and an array of integers <code>primes</code>, return <em>the</em> <code>n<sup>th</sup></code> <em><strong>super ugly number</strong></em>.</p>

<p>The <code>n<sup>th</sup></code> <strong>super ugly number</strong> is <strong>guaranteed</strong> to fit in a <strong>32-bit</strong> signed integer.</p>

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

<pre>
<strong>Input:</strong> n = 12, primes = [2,7,13,19]
<strong>Output:</strong> 32
<strong>Explanation:</strong> [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19].
</pre>

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

<pre>
<strong>Input:</strong> n = 1, primes = [2,3,5]
<strong>Output:</strong> 1
<strong>Explanation:</strong> 1 has no prime factors, therefore all of its prime factors are in the array primes = [2,3,5].
</pre>

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

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= primes.length &lt;= 100</code></li>
	<li><code>2 &lt;= primes[i] &lt;= 1000</code></li>
	<li><code>primes[i]</code> is <strong>guaranteed</strong> to be a prime number.</li>
	<li>All the values of <code>primes</code> are <strong>unique</strong> and sorted in <strong>ascending order</strong>.</li>
</ul>

class Solution {
public:
    int nthSuperUglyNumber(const size_t n, vector<int>& primes) {
        std::set<uint32_t> ugly_numbers;
        std::reverse(primes.begin(), primes.end());
        GenUglyNumbers_r(ugly_numbers, 1, primes, n);
        size_t i = 0;
        for (auto it = ugly_numbers.begin(); it != ugly_numbers.end(); ++it) {
            if (i == n - 1)
                return *it;
            ++i;
        }
        return 0;
    }

    void GenUglyNumbers_r(std::set<uint32_t>& res, uint32_t cur,
                          std::span<const int> factors_left,
                          const size_t max_num) {

        const uint32_t factor = factors_left.front();
        factors_left = factors_left.subspan(1);

        if (factors_left.empty()) {
            while (true) {
                res.insert(cur);
                if (res.size() > max_num)
                {
                    res.erase(std::prev(res.end()));
                    if(cur >= *std::prev(res.end()))
                        break;
                }

                //uint32_t limit = 0x7FFFFFFF;
                //if (res.size() >= max_num)
                 //   limit = ;

                if (cur > 0x7FFFFFFF / factor)
                    break;
                cur *= factor;
            }
        } else {
            while (true) {

                GenUglyNumbers_r(res, cur, factors_left, max_num);

                uint32_t limit = 0x7FFFFFFF;
                if (res.size() >= max_num)
                    limit = *std::prev(res.end());

                if (cur > limit / factor)
                    break;
                cur *= factor;
            }
        }
    }
};
79250