ugly number


Ugly Number

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
public int (int num, int div) {
while (num % div == 0)
num /= div;
return num;
}

public boolean helper(int num) {
num = divider(num, 2);
num = divider(num, 3);
num = divider(num, 5);
if (num == 1)
return true;
return false;
}

public boolean isUgly(int num) {
if (num == 1)
return true;
if (num <= 0)
return false;

for (int i = 2; i <= 5; ++i) {
while (num % i == 0)
num /= i;
}
return num == 1;
}

Ugly Number II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int nthUglyNumber(int n) {
PriorityQueue<Long> q = new PriorityQueue<>();
q.offer(1l);
long val = 0;
HashSet<Long> visited = new HashSet<>();
for (int i = 1; i <= n; ++i) {
val = q.poll();
if (visited.contains(val * 2) == false) {
visited.add(val * 2);
q.offer(val * 2);
}
if (visited.contains(val * 3) == false) {
visited.add(val * 3);
q.offer(val * 3);
}
if (visited.contains(val * 5) == false) {
visited.add(val * 5);
q.offer(val * 5);
}
}
return (int)val;
}