313

313. Super Ugly Number (Medium)

A super ugly number is a positive integer whose prime factors are in the array primes.

Given an integer n and an array of integers primes, return the nth super ugly number.

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

 

Example 1:

Input: n = 12, primes = [2,7,13,19]
Output: 32
Explanation: [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].

Example 2:

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

 

Constraints:

• 1 <= n <= 105
• 1 <= primes.length <= 100
• 2 <= primes[i] <= 1000
• primes[i] is guaranteed to be a prime number.
• All the values of primes are unique and sorted in ascending order.

Companies: Google

Related Topics:
Array, Math, Dynamic Programming

Similar Questions:

• Ugly Number II (Medium)

Solution 1.

v[i] is the i-th super ugly number. v[0] = 1.

Assume we've already computed v[0..i]. The next v[i+1] must be some v[j] (0 <= j <= i) multiplied by a prime number in primes.

Let p[i] be the index to the next extensible number corresponding to primes[i]. That is, v[p[i]] * primes[i] is the next number extended using primes[i].

2/7/13
v
1

// 1 * 2 is the smallest next extension

7/13  2
v     v
1     2

// 2 * 2 is the smallest next extension

7/13    2
v       v
1     2 4

// 1 * 7 is the smallest next extension

13    7 2 
v     v v 
1     2 4 7

// 4 * 2 is the smallest next extension

13    7   2
v     v   v 
1     2 4 7 8

// 1 * 13 is the smallest next extension

      7/13 2  
      v    v 
1     2 4  7 8 13

// 2 * 7 and 7 * 2 are the smallest next extensions

      13 7   2
      v  v   v
1     2  4 7 8 13 14

// OJ: https://leetcode.com/problems/super-ugly-number
// Author: github.com/lzl124631x
// Time: O(NP)
// Space: O(max(N, P))
class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<long> v(n, LONG_MAX), p(primes.size(), 0);
        v[0] = 1;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < primes.size(); ++j) v[i] = min(v[i], primes[j] * v[p[j]]);
            for (int j = 0; j < primes.size(); ++j) p[j] += (v[i] == primes[j] * v[p[j]]);
        }
        return v.back();
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/super-ugly-number
// Author: github.com/lzl124631x
// Time: O(NP)
// Space: O(max(N, P))
// Ref: https://discuss.leetcode.com/topic/34841/java-three-methods-23ms-36-ms-58ms-with-heap-performance-explained
class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> v(n, INT_MAX), p(primes.size(), 0), val(primes.size(), 1);
        v[0] = 1;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < primes.size(); ++j) {
                if (v[i - 1] == val[j]) val[j] = v[p[j]++] * primes[j];
                v[i] = min(v[i], val[j]);
            }
        }
        return v[n - 1];
    }
};