10 lines C++


  • 0

    Based on idea from this thread.

    class Solution {
    public:
        int nthUglyNumber(int n) {
            vector<int>dp(n);
            dp[0] = 1;
            int p2 = 0, p3 = 0, p5 = 0;
            for(int i = 1; i < n; i++){
                dp[i] = min(dp[p2] * 2, min(dp[p3] * 3, dp[p5] * 5));
                if(dp[i] == dp[p2] * 2) p2++;
                if(dp[i] == dp[p3] * 3) p3++;
                if(dp[i] == dp[p5] * 5) p5++;
            }
            return dp[n - 1];
        }
    };
    

    And 3ms 90.86% precompution using static vector.

    class Solution {
    public:
        int nthUglyNumber(int n) {
            static vector<int>dp;
            if(dp.empty()){
                dp.resize(1691);
                dp[0] = 1;
                int p2 = 0, p3 = 0, p5 = 0;
                for(int i = 1; i < 1691; i++){
                    dp[i] = min(dp[p2] * 2, min(dp[p3] * 3, dp[p5] * 5));
                    if(dp[i] == dp[p2] * 2) p2++;
                    if(dp[i] == dp[p3] * 3) p3++;
                    if(dp[i] == dp[p5] * 5) p5++;
                }
            }
            return dp[n - 1];
        }
    };
    

Log in to reply
 

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