Description
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:
Solutions
Solution 1
1
2
3
4
5
6
7
8
9
10
11
12
13 | class Solution:
def nthUglyNumber(self, n: int) -> int:
h = [1]
vis = {1}
ans = 1
for _ in range(n):
ans = heappop(h)
for v in [2, 3, 5]:
nxt = ans * v
if nxt not in vis:
vis.add(nxt)
heappush(h, nxt)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | class Solution {
public int nthUglyNumber(int n) {
Set<Long> vis = new HashSet<>();
PriorityQueue<Long> q = new PriorityQueue<>();
int[] f = new int[] {2, 3, 5};
q.offer(1L);
vis.add(1L);
long ans = 0;
while (n-- > 0) {
ans = q.poll();
for (int v : f) {
long next = ans * v;
if (vis.add(next)) {
q.offer(next);
}
}
}
return (int) ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public:
int nthUglyNumber(int n) {
priority_queue<long, vector<long>, greater<long>> q;
q.push(1l);
unordered_set<long> vis{{1l}};
long ans = 1;
vector<int> f = {2, 3, 5};
while (n--) {
ans = q.top();
q.pop();
for (int& v : f) {
long nxt = ans * v;
if (!vis.count(nxt)) {
vis.insert(nxt);
q.push(nxt);
}
}
}
return (int) ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 | func nthUglyNumber(n int) int {
h := IntHeap([]int{1})
heap.Init(&h)
ans := 1
vis := map[int]bool{1: true}
for n > 0 {
ans = heap.Pop(&h).(int)
for _, v := range []int{2, 3, 5} {
nxt := ans * v
if !vis[nxt] {
vis[nxt] = true
heap.Push(&h, nxt)
}
}
n--
}
return ans
}
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | /**
* @param {number} n
* @return {number}
*/
var nthUglyNumber = function (n) {
let dp = [1];
let p2 = 0,
p3 = 0,
p5 = 0;
for (let i = 1; i < n; ++i) {
const next2 = dp[p2] * 2,
next3 = dp[p3] * 3,
next5 = dp[p5] * 5;
dp[i] = Math.min(next2, Math.min(next3, next5));
if (dp[i] == next2) ++p2;
if (dp[i] == next3) ++p3;
if (dp[i] == next5) ++p5;
dp.push(dp[i]);
}
return dp[n - 1];
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | public class Solution {
public int NthUglyNumber(int n) {
int[] dp = new int[n];
dp[0] = 1;
int p2 = 0, p3 = 0, p5 = 0;
for (int i = 1; i < n; ++i) {
int next2 = dp[p2] * 2, next3 = dp[p3] * 3, next5 = dp[p5] * 5;
dp[i] = Math.Min(next2, Math.Min(next3, next5));
if (dp[i] == next2) {
++p2;
}
if (dp[i] == next3) {
++p3;
}
if (dp[i] == next5) {
++p5;
}
}
return dp[n - 1];
}
}
|
Solution 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | class Solution:
def nthUglyNumber(self, n: int) -> int:
dp = [1] * n
p2 = p3 = p5 = 0
for i in range(1, n):
next2, next3, next5 = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5
dp[i] = min(next2, next3, next5)
if dp[i] == next2:
p2 += 1
if dp[i] == next3:
p3 += 1
if dp[i] == next5:
p5 += 1
return dp[-1]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n];
dp[0] = 1;
int p2 = 0, p3 = 0, p5 = 0;
for (int i = 1; i < n; ++i) {
int next2 = dp[p2] * 2, next3 = dp[p3] * 3, next5 = dp[p5] * 5;
dp[i] = Math.min(next2, Math.min(next3, next5));
if (dp[i] == next2) ++p2;
if (dp[i] == next3) ++p3;
if (dp[i] == next5) ++p5;
}
return dp[n - 1];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | 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) {
int next2 = dp[p2] * 2, next3 = dp[p3] * 3, next5 = dp[p5] * 5;
dp[i] = min(next2, min(next3, next5));
if (dp[i] == next2) ++p2;
if (dp[i] == next3) ++p3;
if (dp[i] == next5) ++p5;
}
return dp[n - 1];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | func nthUglyNumber(n int) int {
dp := make([]int, n)
dp[0] = 1
p2, p3, p5 := 0, 0, 0
for i := 1; i < n; i++ {
next2, next3, next5 := dp[p2]*2, dp[p3]*3, dp[p5]*5
dp[i] = min(next2, min(next3, next5))
if dp[i] == next2 {
p2++
}
if dp[i] == next3 {
p3++
}
if dp[i] == next5 {
p5++
}
}
return dp[n-1]
}
|