Ugly Number II

LeetCode Q 263 - Ugly Number II

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Solution

Code: Method 1

public int nthUglyNumber(int n) {
	List<Integer> uglys = new ArrayList<>();
	uglys.add(1);
	// p2, p3 & p5 share the same queue: uglys
	int p2 = 0, p3 = 0, p5 = 0; 
	for (int i = 1; i < n; i++) {
		int lastNumber = uglys.get(i - 1);
		while (uglys.get(p2) * 2 <= lastNumber) p2++;
		while (uglys.get(p3) * 3 <= lastNumber) p3++;
		while (uglys.get(p5) * 5 <= lastNumber) p5++;
		uglys.add(Math.min(Math.min(uglys.get(p2) * 2, uglys.get(p3) * 3), uglys.get(p5) * 5));
	}
	return uglys.get(n - 1);
}

Code: Set + Heap
Note: Since num * 2, num2 = num * 3, num3 = num * 5 has a potential to cause integer overflow, we need to use Long to store the number.

public int nthUglyNumber(int n) {
	//Set<Integer> set = new HashSet<>(); 
    Set<Long> set = new HashSet<>();
    PriorityQueue<Long> que = new PriorityQueue<>();
    que.offer(1L); set.add(1L);
    long num = 0;
    for (int i = 1; i <= n; i++) {
        num = que.poll();
        long num1 = num * 2, num2 = num * 3, num3 = num * 5; // integer overflow
        if (set.add(num1)) que.offer(num1);
        if (set.add(num2)) que.offer(num2);
        if (set.add(num3)) que.offer(num3);
    }
    return (int) num;
}