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. 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.

Method 1: Min Heap

Analysis

Every time get the smallest number from the min heap and multiply it by 2, 3, 5, and put the result into the heap if there haven't existed before.

Corner Case

1. Need to deal with overflow carefully.

Complexity

Time: O(klgk), each operation to the heap is O(lgk) time

Space: O(k)

Code

Java

public class Solution {
  private static final int[] FACTORS = {2, 3, 5};
  public int nthUglyNumber(int n) {
    Queue<Integer> pq = new PriorityQueue<>();
    Set<Integer> visitedSet = new HashSet<>();
    pq.offer(1);
    for (int i = 0; i < n - 1; i++) {
      int num = pq.poll();
      for (int factor : FACTORS) {
        if (num > Integer.MAX_VALUE / factor) {  // overflow
          continue;
        }
        int newUglyNumber = num * factor;
        if (!visitedSet.contains(newUglyNumber)) {
          pq.offer(newUglyNumber);
          visitedSet.add(newUglyNumber);
        }
      }
    }
    return pq.poll();
  }
}

Method 2: DP

Analysis

The new number must be the smallest one generated by multiply 3, 5, 7 to the existing number already in the array.

We can keep 3 pointers keep track of the numbers that need to be multiple by 3, 5, 7. when the smallest number is generated by 3/5/7, updating the corresponding pointer by one, because each exising number is only meaningful to be multiplied by the same factor once.

We cannot use if else for checking which prime number (3, 5, or 7) yields the smallest product as there may be duplicates. (e.g. 3 x 5 == 5 x 3)

Complexity

Time: O(k)

Space: O(k)

Code

Java

public class Solution {
  public int nthUglyNumber(int n) {
    int[] uglyNumbers = new int[n];
    uglyNumbers[0] = 1;
    int i2 = 0;
    int i3 = 0;
    int i5 = 0;
    for (int i = 1; i < n; i++) {
      uglyNumbers[i] = Math.min(
          uglyNumbers[i2] * 2, 
          Math.min(uglyNumbers[i3] * 3, uglyNumbers[i5] * 5));
      if (uglyNumbers[i] / uglyNumbers[i2] == 2) {
        i2++;
      }
      if (uglyNumbers[i] / uglyNumbers[i3] == 3) {
        i3++;
      }
      if (uglyNumbers[i] / uglyNumbers[i5] == 5) {
        i5++;
      }
    }
    return uglyNumbers[n - 1];
  }
}