Ugly Number II Problem


Description

LeetCode Problem 264.

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the n^th ugly number.

Example 1:

1
2
3
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.

Example 2:

1
2
3
Input: n = 1
Output: 1
Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

Constraints:

  • 1 <= n <= 1690


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int nthUglyNumber(int n) {
        priority_queue<long long int, vector<long long int>, greater<long long int>> pq;
        pq.push(1);
        
        int idx = 0;
        long long int top;
        while (idx < n) {
            top = pq.top();
            
            pq.push(top*2);
            pq.push(top*3);
            pq.push(top*5);
            
            while (!pq.empty() && pq.top() == top)
                pq.pop();
            
            idx ++;
        }
        return top;
    }
};




Related Posts

K-Th Smallest Prime Fraction Problem

LeetCode 786. You are given a sorted integer array arr...

Course Schedule III Problem

LeetCode 630. There are n different online courses numbered from...

IPO Problem

LeetCode 502. Suppose LeetCode will start its IPO soon. In...

Sliding Window Median Problem

LeetCode 480. The median is the middle value in an...

Relative Ranks Problem

LeetCode 506. You are given an integer array score of...

Ugly Number II Problem

LeetCode 264. An ugly number is a positive integer whose...