264. Ugly Number II

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:

1. 1 is typically treated as an ugly number.
2. n does not exceed 1690.

Solution

Approach 1: Three queues.

Approach 2: Minumum heap.

Approach 3: generate the next ugly number one at a time, keeping pointers to each 2, 3, or 5 numbers to multiply next.

Code (Python)

Approach 3:

class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        # time O(n), space O(n)
        nums = [1]
        p2, p3, p5 = 0,0,0
        while len(nums) < n:
            nums.append(min(nums[p2] * 2, nums[p3] * 3, nums[p5] * 5))
            # because of cases like 2 * 3 == 3 * 2, need to check/move all pointers to eliminate duplicates
            if nums[p2] * 2 == nums[-1]:
                p2 += 1
            if nums[p3] * 3 == nums[-1]:
                p3 += 1
            if nums[p5] * 5 == nums[-1]:
                p5 += 1
        return nums[-1]

Code (C++)

Approach 1:

// Three queues.
class Solution {
public:
    int nthUglyNumber(int n) {
        if (n == 0)
            return 0;
        queue<long> q2;
        queue<long> q3;
        queue<long> q5;
        long res = 1;
        for (int i = 2; i <= n; ++i)
        {
            q2.push(res * 2);
            q3.push(res * 3);
            q5.push(res * 5);
            res = std::min(std::min(q2.front(), q3.front()), q5.front());
            if (q2.front() == res)
                q2.pop();
            if (q3.front() == res)
                q3.pop();
            if (q5.front() == res)
                q5.pop();
        }
        return res;
    }
};

Approach 2:

// Minumum heap.
class Solution {
public:
    int nthUglyNumber(int n) {
        if (n == 0)
            return 0;
        priority_queue<long, vector<long>, greater<long>> minHeap;
        minHeap.push(1);
        long res = 1;
        for (int i = 2; i <= n; ++i)
        {
            while (!minHeap.empty() && minHeap.top() == res)
                minHeap.pop();
            minHeap.push(res * 2);
            minHeap.push(res * 3);
            minHeap.push(res * 5);
            res = minHeap.top();
        }
        return res;
    }
};