My 8ms Java DP solution


  • 5
    A

    My 8ms JAVA DP Solution

    public int nthUglyNumber(int n) {

        if( n == 0 || n == 1) {
            return n;
        }
        
        int pointer2 = 0;
        int pointer3 = 0;
        int pointer5 = 0;
        
        int[] result = new int[n];
        result[0] = 1;
    
        int i = 1, min =0;
        while ( i < n ) {
            min = Math.min(result[pointer2]*2,Math.min(result[pointer3]*3,result[pointer5]*5));
            
            if(min == result[pointer2]*2) {
                pointer2++;
            }
            if(min == result[pointer3]*3) {
                pointer3++;
            }
            if(min == result[pointer5]*5) {
                pointer5++;
            }
            result[i] = min;
         
            i++;
            
        }
        return result[n-1];
    }

  • 0
    C

    Very neat solution. Great idea of using 3 pointers on result array!


  • 0

    @akash8 Nice! But I am confused that what do the pointer2 pointer3 and pointer5 actually point to??


  • 0
    A

    @keZhenxu All three pointers pointer2 pointer3 and pointer5 actually points to the current count for each number 2,3, and 5.


  • 0
    D

    @keZhenxu the pointers point to the next ugly number in the ugly number sequence, that they are going to be multiplied to.

    For instance, at the beginning the array contains only one element, [1], so all of the pointers point to the position 0.
    At the first iteration, the values are 2,3,5 (1 * 2, 1 * 3, 1 * 5). The min element is 2, so we increment the 2's pointer.

    Currently our array is [1,2] so the 2s pointers should be updated to 1 (just incremented, pointer2++), because it makes no sense to multiply it to 1 anymore, since it will result a much smaller result, than to last element of the array. I guess you've understood the logic.

    P.S. I also came to this algorithm. Maybe because of the hints :(


  • 0

    @denis631 Thank you very much!!


  • 0

    @akash8 Thank you very much!!


  • 0
    L

    That's brilliant!
    Thanks a lot.


Log in to reply
 

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