Thinking process

what is an ugly number? what is the pattern that can be found from the first 10 ugly number?

• 1, 1x2, 1x3, 2x2, 1x5, 3x2, 4x2, 3x3, 2x5 .....
• Similar to find the kth number in a ordered matrix, add the next possible values to a min heap, and poll out the currently smallest

How to know what numbers added next?

• the next number should be current smallest multiply by 2 or 3 or 5

Mistakes

• int vs long

  • int can only hold 32-bit integers
  • long can hold 64 bits

• don't forget to skip duplicates.

public class Solution {
    public int nthUglyNumber(int n) {
        //validate input
        if (n == 0) return 0;

        PriorityQueue<Long> pq = new PriorityQueue<>();//min heap
        pq.add(1l);

        while (!pq.isEmpty() && n > 1) {
            long num = pq.poll();
            while (!pq.isEmpty() && pq.peek() == num) pq.poll();
            pq.add(num * 2);
            pq.add(num * 3);
            pq.add(num * 5);
            n--;
        }

        return pq.poll().intValue();
    }
}

Optimize to linear

Instead of calculating all the possible values after poll out one number, calculate one each time.

public class Solution {
    public int nthUglyNumber(int n) {
        //validate input
        if (n == 0) return 0;

        int[] uglyNums = new int[n];
        uglyNums[0] = 1;

        int index2 = 0, index3 = 0, index5 = 0;
        int fac2 = 2, fac3 = 3, fac5 = 5;

        for (int i = 1; i < n; ++i) {
            int min = Math.min(Math.min(fac2, fac3), fac5);
            uglyNums[i] = min;
            if (fac2 == min) {
                fac2 = 2 * uglyNums[++index2];
            }
            if (fac3 == min) {
                fac3 = 3 * uglyNums[++index3];
            }
            if (fac5 == min) {
                fac5 = 5 * uglyNums[++index5];
            }
        }

        return uglyNums[n - 1];
    }
}