Ugly Number II

Description

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

Design an algorithm to find the nth ugly number. The first 10 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

Notice
Note that 1 is typically treated as an ugly number.

Example
If n=9, return 10.

Challenge:
O(n log n) or O(n) time.

Link

Lintcode_ladder

Method

1. Use an accumuated vector to record minimum ugly number. THe minimum ugly nubmer is the minimum product of 2/3/5 * nums[an index]
2. x

Example

1. 1

class Solution {
public:
    /*
     * @param n an integer
     * @return the nth prime number as description.
     */
    int nthUglyNumber(int n) {
        // write your code here
        if (n == 0) {
            return -1;
        }
        // nums record the n ugly number
        vector<int> nums;
        nums.push_back(1);
        int cur = 2;
        // p1 p2 p3 record the index of nums
        // we use the nums[index] to multiply 2/3/5 
        // finding minimum next ugly number
        int p1 = 0;
        int p2 = 0;
        int p3 = 0;
        int min1, min2, min3;
        while (nums.size() < n) {
            // for 2 factor
            while (nums[p1] * 2 < cur) {
                p1++;
            }
            min1 = nums[p1] * 2;
            // for 3 factor
            while (nums[p2] * 3 < cur) {
                p2++;
            }
            min2 = nums[p2] * 3;
            // for 5 factor
            while (nums[p3] * 5 < cur) {
                p3++;
            }
            min3 = nums[p3] * 5;
            // finding current min
            int newugly = min(min1, min(min2, min3));
            nums.push_back(newugly);
            cur = newugly + 1;
        }
        return nums[n-1];
    }
};

Similar problems

x

Tags

x