313. Super Ugly Number (Medium)

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [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] of size 4.

Note:

(1) 1 is a super ugly number for any given primes.

(2) The given numbers in primes are in ascending order.

(3) $$0 < k ≤ 100$$, $$0 < n ≤ 10^6$$, 0 < primes[i] < 1000.

(4) The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

Solution 1:

126ms

每次都找到第i个最小值，更新idx为下一个开始相乘的位置。

int nthSuperUglyNumber(int n, vector<int>& primes) {
    int p = primes.size();
    vector<int> idx(p, 0), ugly(n);
    ugly[0] = 1;
    for (int i = 1; i < n; ++i) {
        ugly[i] = INT_MAX;
        //find next
        for (int j = 0; j < p; ++j) ugly[i] = min(ugly[i], ugly[idx[j]]*primes[j]);
        // slip duplicates
        for (int j = 0; j < p; ++j) {
            if (ugly[idx[j]]*primes[j] == ugly[i]) ++idx[j];
        }
    }
    return ugly[n-1];
}

Solution 2:

Time Complexity: O(kN) 89 ms

If you look at the above solution, it has redundant multiplication can be avoided, and also two for loops can be consolidated into one. This trade-off space for speed.

int nthSuperUglyNumber(int n, vector<int>& primes) {
    int p = primes.size(), next = 1;
    vector<int> idx(p, 0), val(p,1), ugly(n);

    for (int i = 0; i < n; ++i) {
        ugly[i] = next;
        next = INT_MAX;
        for (int j = 0; j < p; ++j) {
            if (val[j] == ugly[i]) val[j] = ugly[idx[j]++]*primes[j];
            next = min(next, val[j]);
        }
    }
    return ugly[n-1];
}