313. Super Ugly Number

We uses num[i] to save the ith ugly number. The basic idea is the new ugly number nums[i] is the minimum product of numbers before nums[i] and primes. If we solve it in a brute force way, the running time will be O(n*n*k), where k is the primes size. However, we can keep for each prime the last index that it has been applied. This will reduce the running time to O(n*k).

For example, at the very beginning, the index will be 0 for all primes because num[0] (which is 1) will be the first to multiply. Now let's look at line 7 - 14.

Round 1: nums[1] = 2 (because 2 is the minimum product of 1 * primes[j]). And since 2 has been applied, we increase the index for 2 to 1.

Round 2: nums[2] = 4 (because 2*2 is still less than any other product of 1 * primes[j]). And since 2 has been applied, we increase the index for 2 to 2.

Round 3: nums[3] = 7 (because 1*7 is less than product of 2 * 4 and any other product of 1 * primes[j]). And since 7 has been applied, we increase the index for 7 to 1.

Keep doing that until we reach n.

1:  class Solution {  
2:  public:  
3:    int nthSuperUglyNumber(int n, vector<int>& primes) {  
4:      vector<int> index(primes.size(), 0);  
5:      vector<int> nums(n, INT_MAX);  
6:      nums[0] = 1;  
7:      for (int i = 1; i < n; i++) {  
8:        for (int j = 0; j < primes.size(); j++) {  
9:          nums[i] = min(nums[i], primes[j]*nums[index[j]]);  
10:        }  
11:        for (int j = 0; j < primes.size(); j++) {  
12:          if (primes[j]*nums[index[j]] == nums[i]) index[j]++;  
13:        }  
14:      }  
15:      return num[n-1];  
16:    }  
17:  };