# Leetcode Ugly Number II problem solution

In this Leetcode Ugly Number II problem solution An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. we have given an integer n, return true if nth is an ugly number.

## Problem solution in Python.

```class Solution:
def nthUglyNumber(self, n: int) -> int:
# DP cache
dp = [0]*n
# DP base case
dp[0] = 1
# DP step case
i2 = i3 = i5 = 0
for i in range(1, n):
k = min(dp[i2]*2, dp[i3]*3, dp[i5]*5) # Next ugly number
dp[i] = k
if dp[i] == dp[i2]*2:
i2 = i2+1
if dp[i] == dp[i3]*3:
i3 = i3+1
if dp[i] == dp[i5]*5:
i5 = i5+1
return dp[n-1]
```

## Problem solution in Java.

```class Solution{
public int nthUglyNumber(int n) {
ArrayList<Integer> l= new ArrayList<>();
int i2=0,i3=0,i5=0;
while(l.size()<n){
int m2 = l.get(i2)*2;
int m3 = l.get(i3)*3;
int m5 = l.get(i5)*5;
int min = Math.min(m2, Math.min(m3, m5));
if(min==m2)
i2++;
if(min==m3)
i3++;
if(min==m5)
i5++;
}
return l.get(l.size()-1);
}
}
```

## Problem solution in C++.

```class Solution {
public:
int nthUglyNumber(int n) {
priority_queue<long int, vector<long int>, greater<long int> > q;
q.push(1);
unordered_set<long int> walked;
walked.insert(1);
for(int i=0; i<n-1; i++){
long int tmp=q.top();
q.pop();
if(tmp>=INT_MAX/2)continue;
if(walked.find(tmp*2)==walked.end()){
q.push(tmp*2);
walked.insert(tmp*2);
}
if(walked.find(tmp*3)==walked.end()){
q.push(tmp*3);
walked.insert(tmp*3);
}
if(walked.find(tmp*5)==walked.end()){
q.push(tmp*5);
walked.insert(tmp*5);
}
}
return q.top();

}
};
```

## Problem solution in C.

```#define min(x,y) (x < y ? x : y)

int nthUglyNumber(int n) {
static int arr[1691] = {[0]= 1},
i  = 1, i2 = 0, i3 = 0, i5 = 0,
n2 = 2, n3 = 3, n5 = 5;

for (; i < n; i++) {
arr[i] = min(min(n2, n3), n5);
if (arr[i] == n2) n2 = 2 * arr[++i2];
if (arr[i] == n3) n3 = 3 * arr[++i3];
if (arr[i] == n5) n5 = 5 * arr[++i5];
}

return arr[n-1];
}
```