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

Given an integer n, return the nth ugly number.

&nbsp;
Example 1:

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:

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


&nbsp;
Constraints:


	1 &lt;= n &lt;= 1690


import heapq
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        h1, h2, h3 = [], [], []
        heapq.heappush(h1, 1)
        heapq.heappush(h2, 1)
        heapq.heappush(h3, 1)
        ugly_number = 1
        last_ugly_number = 1
        count = 1
        while count < n:
            if 2 * h1[0] <= 3 * h2[0] and 2 * h1[0] <= 5 * h3[0]:
                # pop from h1
                x = heapq.heappop(h1)
                ugly_number = 2 * x
                if ugly_number == last_ugly_number:
                    # do nothing
                    continue
                count+=1
                last_ugly_number = ugly_number
                heapq.heappush(h1, ugly_number)
                heapq.heappush(h2, ugly_number)
                heapq.heappush(h3, ugly_number)

            elif 3 * h2[0] <= 2 * h1[0] and 3 * h2[0] <= 5 * h3[0]:
                # pop from h2
                x = heapq.heappop(h2)
                ugly_number = 3 * x
                if ugly_number == last_ugly_number:
                    continue
                count+=1
                last_ugly_number = ugly_number
                heapq.heappush(h1, ugly_number)
                heapq.heappush(h2, ugly_number)
                heapq.heappush(h3, ugly_number)
            else:
                # pop from h3
                x = heapq.heappop(h3)
                ugly_number = 5 * x
                if ugly_number == last_ugly_number:
                    continue
                count+=1
                last_ugly_number = ugly_number
                heapq.heappush(h1, ugly_number)
                heapq.heappush(h2, ugly_number)
                heapq.heappush(h3, ugly_number)

        return last_ugly_number
// Ugly number II
// https://leetcode.com/problems/ugly-number-ii/

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        int i2 = 0, i3 = 0, i5 = 0;
        for (int i = 1; i < n; i++) {
            dp[i] = Math.min(dp[i2] * 2, Math.min(dp[i3] * 3, dp[i5] * 5));
            if (dp[i] == dp[i2] * 2) i2++;
            if (dp[i] == dp[i3] * 3) i3++;
            if (dp[i] == dp[i5] * 5) i5++;
        }
        return dp[n - 1];
    }
}
class Solution {
public:
    int nthUglyNumber(int n) {

        int dp[n+1];
        dp[1] = 1;

        int p2 = 1, p3 = 1, p5 = 1;
        int t;

        for(int i = 2; i < n+1; i++){
            t = min(dp[p2]*2, min(dp[p3]*3, dp[p5]*5));
            dp[i] = t;

            if(dp[i] == dp[p2]*2){
                p2++;
            }
            if(dp[i] == dp[p3]*3){
                p3++;
            }
            if(dp[i] == dp[p5]*5){
                p5++;
            }
        }
        return dp[n];

    }
};
var nthUglyNumber = function(n) {
let uglyNo = 1;
let uglySet = new Set(); // Set to keep track of all the ugly Numbers to stop repetition
uglySet.add(uglyNo);
let minHeap = new MinPriorityQueue(); // Javascript provides inbuilt min and max heaps, constructor does not require callback function for primitive types but a comparator callback for object data types, to know which key corresponds to the priority
//callback looks like this new MinPriorityQueue((bid) => bid.value)
// if this is confusing, check the documentation here
// https://github.com/datastructures-js/priority-queue/blob/master/README.md#constructor
while(n>1){
    if(!uglySet.has(uglyNo*2)){// add only if the set does not have this ugly no.
        minHeap.enqueue(uglyNo*2,uglyNo*2);// enqueue takes two inputs element and priority respectively, both are same here
        uglySet.add(uglyNo*2);
    }
    if(!uglySet.has(uglyNo*3)){
        minHeap.enqueue(uglyNo*3,uglyNo*3);
        uglySet.add(uglyNo*3);
    }
    if(!uglySet.has(uglyNo*5)){
        minHeap.enqueue(uglyNo*5,uglyNo*5);
        uglySet.add(uglyNo*5);
    }
    uglyNo = minHeap.dequeue().element;//dequeue returns an object with two properties priority and element
    n--;
}

return uglyNo;
};
Ugly Number II