# 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 is typically treated as an ugly number.
- 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;
}
};