ugly number I && II

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. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

The first one is quite easy, if a number cannot be divided by 2, 3 or 5, it's not an ugly number. Other wise, divide it by 2, 3, 5 and recursively check the quotient.

public boolean isUgly(int num) {
        if (num <= 0)
            return false;
        else if (num == 1 || num == 2 || num == 3 ||  num == 5)
            return true;
        else 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;
            
    }

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.

Hint:

1. The naive approach is to call isUgly for every number until you reach the nth one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.
2. An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
3. The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L1, L2, and L3.
4. Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 * 2, L2 * 3, L3 * 5).

The second one is a little bit tricky. Since we don't want to check all numbers to see if it is ugly, we can generate it from previous ugly number. The first one is 1, then the number can be generated by multiply 2, 3, and 5. Every ugly number can be used to generate later numbers. Thus we can refer to merge sort idea, create an array of 3 to check the index of last ugly generated by current prime number. We compare the products of the three primes and their last ugly numbers and get the minimum, add to our array, until we find the nth number. Note if there are two numbers equal, we increment of the indices to avoid duplication.

    public int nthUglyNumber(int n) {
        if (n == 1) {
            return 1;
        }
        int[] nums = new int[n];
        nums[0] = 1;
        int[] primes = {2, 3, 5};
        int[] indices = new int[3];
        for (int i = 1; i < n; i++) {
            int min = Integer.MAX_VALUE, min_index = 0;
            for (int j = 0; j < 3; j++) {
                int curr = nums[indices[j]] * primes[j];
                if (curr < min) {
                    min = curr;
                    min_index = j;
                } else if (curr == min) {
                    indices[j]++;
                }
            }
            nums[i] = min;
            indices[min_index]++;
        }
        return nums[n - 1];
    }