Ugly Number

Ugly number is a number that only have factors 3, 5 and 7.

Design an algorithm to find the Kth ugly number. The first 5 ugly numbers are 3, 5, 7, 9, 15 ...

Have you met this question in a real interview? 

Yes

Example

If K=4, return 9.

Challenge

O(K log K) or O(K) time.

class Solution {

    /**

     * @param k: The number k.

     * @return: The kth prime number as description.

     */

    public long kthPrimeNumber(int k) {

        // write your code here

        long[] record = new long[k+1];

        record[0] = 1;

        int k3 = 0, k5 = 0, k7 = 0;

        for(int i = 1; i <= k; i++){

            record[i] = Math.min(Math.min(record[k3]*3, record[k5]*5), record[k7]*7);

            if(record[i] / record[k3] == 3) k3++;

            if(record[i] / record[k5] == 5) k5++;

            if(record[i] / record[k7] == 7) k7++;

        }

        return record[k];

    }

};