## Algorithm

Problem Name: 264. Ugly Number II

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.

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.
```

Constraints:

• `1 <= n <= 1690`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int nthUglyNumber(int n) {
int i, u2, u3, u5, k2, k3, k5, k;
int *p, sz;

p  = malloc(n * sizeof(int));
//assert(p);

p[0] = 1;
u2 = u3 = u5 = 0;

for (i = 1; i  <  n; i ++) {  // more like dp solution, 3ms
k2 = p[u2] * 2;
k3 = p[u3] * 3;
k5 = p[u5] * 5;
k = k2  <  k3 ? k2 : k3;
k = k  < k5 ? k  : k5;
if (k == k2) u2 ++;
if (k == k3) u3 ++;
if (k == k5) u5 ++;
p[i] = k;
}

k = p[n - 1];
free(p);

return k;
}
``````
Copy The Code &

Input

cmd
n = 10

Output

cmd
12

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int nthUglyNumber(int n) {
vector<int>dp(n);
dp[0] = 1;
int p2 = 0, p3 = 0, p5 = 0;
for(int i = 1; i  <  n; i++){
dp[i] = min(dp[p2] * 2, min(dp[p3] * 3, dp[p5] * 5));
if(dp[i] == dp[p2] * 2) p2++;
if(dp[i] == dp[p3] * 3) p3++;
if(dp[i] == dp[p5] * 5) p5++;
}
return dp[n - 1];
}
};
``````
Copy The Code &

Input

cmd
n = 10

Output

cmd
12

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int nthUglyNumber(int n) {
int[] arr = new int[n];
arr[0] = 1;
int idx2 = 0;
int idx3 = 0;
int idx5 = 0;
int mul2 = 2;
int mul3 = 3;
int mul5 = 5;
int ugly = arr[0];
for (int i = 1; i  <  n; i++) {
ugly = Math.min(mul2, Math.min(mul3, mul5));
arr[i] = ugly;
if (ugly == mul2) {
idx2++;
mul2 = arr[idx2] * 2;
}
if (ugly == mul3) {
idx3++;
mul3 = arr[idx3] * 3;
}
if (ugly == mul5) {
idx5++;
mul5 = arr[idx5] * 5;
}
}
return ugly;
}
}
``````
Copy The Code &

Input

cmd
n = 1

Output

cmd
1

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const nthUglyNumber = function (n) {
if (n <= 0) return false
if (n === 1) return true
let t2 = 0,
t3 = 0,
t5 = 0
const k = Array(n).fill(1)
k[0] = 1
for (let i = 1; i  <  n; i++) {
k[i] = Math.min(k[t2] * 2, k[t3] * 3, k[t5] * 5)
if (k[i] == k[t2] * 2) t2++
if (k[i] == k[t3] * 3) t3++
if (k[i] == k[t5] * 5) t5++
}
return k[n - 1]
}
``````
Copy The Code &

Input

cmd
n = 1

Output

cmd
1

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def nthUglyNumber(self, n):
arr, heap, used = [], [1], set()
for i in range(n):
num = heapq.heappop(heap)
arr.append(num)
for p in (2, 3, 5):
if p * num not in used:
heapq.heappush(heap, p * num)
return arr[-1]
``````
Copy The Code &

Input

cmd
n = 10

Output

cmd
12

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _0264_UglyNumberII
{
private readonly int[] numbers = new int[1690];

public int NthUglyNumber(int n)
{
if (n  <  0) return -1;
if (n == 1) return 1;
if (numbers[n - 1] > 0) return numbers[n - 1];

int index2 = 0, index3 = 0, index5 = 0;
numbers[0] = 1;

for (int i = 1; i  <  n; i++)
{
numbers[i] = Math.Min(Math.Min(numbers[index2] * 2, numbers[index3] * 3), numbers[index5] * 5);
if (numbers[i] == numbers[index2] * 2) index2++;
if (numbers[i] == numbers[index3] * 3) index3++;
if (numbers[i] == numbers[index5] * 5) index5++;
}

return numbers[n - 1];
}
}
}
``````
Copy The Code &

Input

cmd
n = 10

Output

cmd
12