Ugly Number

Write a program to check whether a given number is an ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

• Time: O(n)
• Space: O(n)

public boolean isUgly(int num) {
    if (num == 0) {
        return false;
    }
    if (num == 1) {
        return true;
    }
    if (num % 2 == 0) {
        return isUgly(num / 2);
    } else if (num % 3 == 0) {
        return isUgly(num / 3);
    } else if (num % 5 == 0) {
        return isUgly(num / 5);
    } else {
        return false;
    }
}

Ugly Number II

Write a program to find the nth ugly number.

• Time: O(n)
• Space: O(n)

public int nthUglyNumber(int n) {
    int c2 = 0, c3 = 0, c5 = 0;
    int f2 = 2, f3 = 3, f5 = 5;
    int[] ret = new int[n];
    ret[0] = 1;
    for (int i = 1; i < n; i++) {
        ret[i] = Math.min(f2, Math.min(f3, f5));
        if (ret[i] == f2) {
            f2 = 2 * ret[++c2];
        }
        if (ret[i] == f3) {
            f3 = 3 * ret[++c3];
        }
        if (ret[i] == f5) {
            f5 = 5 * ret[++c5];
        }
    }
    return ret[n - 1];
}