# C++ simple solution with explanation

• explanation:
vector next used to record candidate ugly num
idx used to help generate next ugly num
dp used to recode ugly num by index

example:
[2,3,5,7]
the content of next
2,3,5,7
4(primes[0] * dp[++idx[0]] => 2 * dp[++0]),3,5,7
4,6(primes[1] * dp[++idx[1]] => 3 * dp[++0]),5,7
6(primes[0] * dp[++idx[0]] => 2 * dp[++1]),6,5,7
8(primes[0] * dp[++idx[0]] => 2 * dp[++1]), 9 (primes[1] * dp[++idx[1]] => 3 * dp[1++]), 5, 6

the content of dp
1
1,2
1,2,3
1,2,3,4
1,2,3,4,6

``````class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
int k = primes.size();
vector<int> idx(k, 0), next = primes, dp(n, INT_MAX);
dp[0] = 1;

for (int i = 1; i < n; i++) {
for (int j = 0; j < k; j++)
dp[i] = min(dp[i], next[j]);
// update
for (int j = 0; j < k; j++)
if (dp[i] == next[j])
next[j] = primes[j] * dp[++idx[j]];
}
return dp[n - 1];
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.