C++ simple solution with explanation


  • 0

    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];
        }
    };
    

Log in to reply
 

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