Shortest O(n) Java DP solution

  • 27
    public int nthUglyNumber(int n) {
            if(n==1) return 1;
            int[] dp = new int[n+1]; // dp[i] holds the ith's ugly number
            dp[1] = 1;
            int p2=1, p3=1, p5=1;
            for(int i=2; i<=n; i++){ // loop invariant:dp[i] holds the smallest ith uglynumber
                dp[i] = Math.min(2*dp[p2], Math.min(3*dp[p3],5*dp[p5])); // the next ugly number must be built from a smaller ugly number
            return dp[n];

Log in to reply

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