264. Ugly Number II

Problem

Ugly Number II

Approach

1. Firstly, it is easy to check if every number is ugly number. But, it costs too much time in computing these un-ugly numbers and it will result TLE.
2. So, let’s figure out another method. Obviously, all ugly numbers are 2ⁱ3^j4^k. Then, we can generate new ugly numbers by tracking if some ugly number has been multiplied by 2, 3 and 5, which can be tracked by 3 pointers p2 p3 & p5.
3. For example, the init ugly numbers are [1] and pointer2, pointer3 and pointer5 are refering to index 0. Then by comparing 1 * 2, 1 * 3 and 1 * 5, which are ugly[pointer2] * 2, ugly[pointer3] * 3 and ugly[pointer5] * 5, we can get 1 * 2 is minimal and pointer2 can be moved to next index(pointer2 ++) and the new ugly numbers are [1,2]. In the same way, by comparing 2 * 2, 1 * 3 and 1 * 5, 1 * 3 is minimal and pointer3 will be moved to next index and the new ugly numbers are [1,2,3]. And so on…

Code

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        int p2 = 0, p3 = 0, p5 = 0;// pi stands for the number, dp[pi], which is not mulpiplied by i, i = 2,3 or 5
        for(int i = 1; i < n; i ++){
            int min = Math.min(dp[p2] * 2, Math.min(dp[p3] * 3, dp[p5] * 5));
            if(min == dp[p2] * 2) p2 ++;
            if(min == dp[p3] * 3) p3 ++;
            if(min == dp[p5] * 5) p5 ++;
            dp[i] = min;
        }
        return dp[n - 1];
    }
}