Great explanation and Java code for this impressive question!


  • 0
    E

    You can get it after reading follows:
    k[0] = 1;
    k[1] = min(k[0]*2, k[0]*3, k[0]*5) = k[0]*2 = 2;
    k[2] = min(k[1]*2, k[0]*3, k[0]*5) = k[0]*3 = 3;
    k[3] = min(k[1]*2, k[1]*3, k[0]*5) = k[1]*2 = 4;
    k[4] = min(k[2]*2, k[1]*3, k[0]*5) = k[0]*5 = 5;
    k[5] = min(k[2]*2, k[1]*3, k[1]*5) = k[2]*2 = k[1]*3 = 6;
    k[6] = min(k[3]*2, k[2]*3, k[1]*5) = k[3]*2 = 8;
    ......

    coding as follow:

    class Solution {
        public int nthUglyNumber(int n) {
            int t2 = 0, t3 = 0, t5 = 0; 
            int[] u = new int[n];
            u[0] = 1;
            for(int i=1; i<n; i++)
            {
                u[i] = Math.min(u[t2] * 2, Math.min(u[t3] * 3, u[t5] * 5));
                if(u[i] == u[t2] * 2) t2++; 
                if(u[i] == u[t3] * 3) t3++;
                if(u[i] == u[t5] * 5) t5++;
            }
            return u[n-1];
        }
    }
    

Log in to reply
 

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