Ugly Number II

Problem Description

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

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

Solutions
I. Solution using 3 queues
The idea is that we use three queue to store the ugly numbers.
At first, we add 2, 3, 5 to the first queue, second queue and third queue respectively. Each time we choose the smallest number smallest from one of the 3 queues. If it is from the first queue, we add smallest * 2 to the first queue, smallest * 3 to the second queue, and smallest * 5 to the third queue. If it is from the second queue, we only add smallest * 3 to the second queue, and smallest * 5 to the third queue. And finally, if it is from the third queue, we add smallest * 5 to the third queue. This procedure guarantees that there is no duplicate number in all three queues. We continue doing these steps until we find the n-th number.
We can also solve the problem using min heap.

public class Solution {
    public int nthUglyNumber(int n) {
        if(n==1) return 1;
        Queue<Long> q1 = new LinkedList<Long>();
        Queue<Long> q2 = new LinkedList<Long>();
        Queue<Long> q3 = new LinkedList<Long>();
        
        long t = 1;
        q1.add(2L); q2.add(3L); q3.add(5L);
        --n;
        while(n>0){
            if(q1.peek() < q2.peek()){
                if(q1.peek() < q3.peek()){
                    t = q1.remove();
                    q1.add(t*2); q2.add(t*3); q3.add(t*5);
                }else {
                    t = q3.remove();
                    q3.add(t*5);
                }
            }else{
                if(q2.peek() < q3.peek()){
                    t = q2.remove();
                    q2.add(t*3); q3.add(t*5);
                }else {
                    t = q3.remove();
                    q3.add(t*5);
                }
            }
            --n;
        }
        return (int) t;
    }
}

II. Improvement from the previous code
We now make some improvement on the previous code to make it look better.
Below is the code in Python

class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        q1 = [2]
        q2 = [3]
        q3 = [5]
        q = 1
        for i in range(1,n):
            q = min(q1[0], q2[0], q3[0])
            if q == q3[0]:
                q3.pop(0)
            elif q == q2[0]:
                q2.pop(0)
                q2.append(q * 3)
            else:
                q1.pop(0)
                q1.append(q * 2)
                q2.append(q * 3)
                
            q3.append(q * 5) # add to queue 3
        return q

And Java Code:

public class Solution {
    public int nthUglyNumber(int n) {
        Queue<Long> q1 = new LinkedList<Long>();  
        Queue<Long> q2 = new LinkedList<Long>();  
        Queue<Long> q3 = new LinkedList<Long>();
        q1.add(2L); q2.add(3L); q3.add(5L);
        
        long q = 1;
        for (int i = 1; i<n; i++){
            
            q = Math.min(q1.peek(), Math.min(q2.peek(), q3.peek()));
            if (q == q3.peek())
                q3.remove();
            else if(q == q2.peek()){
                q2.remove();
                q2.add( q * 3);
            }else {
                q1.remove();
                q1.add(q * 2);
                q2.add(q * 3);
            }
            q3.add(q * 5);
        }
        
        return (int) q;
    }
}

III. Reduce space used in the solution numbered II
We can reduce the space used in the previous Solution. Below is the python code.

class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1: return 1
        p1, p2, p3 = 0, 0, 0 #pointers in the following list
        
        q = [0] * n
        q[0] = 1
        
        for i in range(1, n):
            t1, t2, t3 = q[p1] * 2, q[p2] * 3, q[p3] * 5
            q[i] = min(t1, t2, t3)
            if q[i] == t1: p1 += 1
            if q[i] == t2: p2 += 1
            if q[i] == t3: p3 += 1
            
        return q[-1]

IV. Using Min Heap
We also can use Min Heap in this problem. Although this approach does not run faster than the above solutions, it is good for us to know how to use additional data structure in order to solve the problem.
Java Code:

public class Solution {
    public int nthUglyNumber(int n) {

        PriorityQueue<Long> minHeap = new PriorityQueue<Long>();
        minHeap.offer(new Long(1L));

        Long uglyNumber = 1L;

        for (int i=1; i<=n; ++i) {
            uglyNumber = minHeap.poll();
            if (!minHeap.contains(uglyNumber * 2)) 
                minHeap.offer(uglyNumber * 2);
            if (!minHeap.contains(uglyNumber * 3)) 
                minHeap.offer(uglyNumber * 3);
            if (!minHeap.contains(uglyNumber * 5)) 
                minHeap.offer(uglyNumber * 5);
        }

        return  uglyNumber.intValue();
    }
}