Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers. Note that 1 is typically treated as an ugly number.

The key is to realize each number can be and have to be generated by a former number multiplied by 2, 3 or 5 e.g. 1 2 3 4 5 6 8 9 10 12 15.. what is next? it must be x * 2 or y * 3 or z * 5, where x, y, z is an existing number. How do we determine x, y, z then? apparently, you can just traverse the sequence generated by far from 1 … 15, until you find such x, y, z that x * 2, y * 3, z * 5 is just bigger than 15. In this case x=8, y=6, z=4. Then you compare x * 2, y * 3, z * 5 so you know next number will be x * 2 = 8 * 2 = 16. k, now you have 1,2,3,4,….,15, 16, Then what is next? You wanna do the same process again to find the new x, y, z, but you realize, wait, do I have to traverse the sequence generated by far again? NO! since you know last time, x=8, y=6, z=4 and x=8 was used to generate 16, so this time, you can immediately know the newx = 9 (the next number after 8 is 9 in the generated sequence), y=6, z=4. Then you need to compare newx * 2, y * 3, z * 5. You know next number is 9 * 2 = 18; And you also know, the next x will be 10 since new_x = 9 was used this time. But what is next y? apparently, if y=6, 6*3 = 18, which is already generated in this round. So you also need to update next y from 6 to 8.

class Solution {
    /**
     * @param k: The number k.
     * @return: The kth prime number as description.
     */
    public long kthPrimeNumber(int k) {
        if (k <= 0) return 0;

        long[] num = new long[k + 1];
        num[0] = 1;
        int index3 = 0, index5 = 0, index7 = 0;
        for (int i = 1; i <= k; i++) {
            num[i] = Math.min(num[index3] * 3, Math.min(num[index5] * 5, num[index7] * 7));
            if (num[index3] * 3 == num[i]) index3++;
            if (num[index5] * 5 == num[i]) index5++;
            if (num[index7] * 7 == num[i]) index7++;
        }
        return num[k];
    }
};

class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """

        dp = [0] * (n + 1)
        dp[1] = 1
        index2 = index3 = index5 = 1
        for i in xrange(2, n + 1):
            dp[i] = min(dp[index2] * 2, dp[index3] * 3, dp[index5] * 5)
            if dp[i] == dp[index2] * 2:
                index2 += 1
            if dp[i] == dp[index3] * 3:
                index3 += 1
            if dp[i] == dp[index5] * 5:
                index5 += 1
        return dp[n]