C++ 6ms 9 lines


  • 3
     int nthUglyNumber(int n) {
            int dp[n]; memset(dp, 0, sizeof(dp)); dp[0] = 1;
            int p2 = 0, p3 = 0, p5 = 0, min2 = 2, min3 = 3, min5 = 5;
            
            for (int i = 1; i < n; i++) {
                dp[i] = min(min2, min(min3, min5));
                if (dp[i] == min2) { min2 = dp[++p2] * 2; }
                if (dp[i] == min3) { min3 = dp[++p3] * 3; }
                if (dp[i] == min5) { min5 = dp[++p5] * 5; }
            }
            
            return dp[n - 1];
        }
    

Log in to reply
 

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