Ugly Number I, Ugly Number II, Super Ugly Number

XXX. Ugly Numbers I, II, and III

Math

Heap

Dynamic Programming

Problem Statement:

The "Ugly Numbers" problems include the following:

1. Ugly Number I: Check if a number is "ugly" (only divisible by 2, 3, or 5).
2. Ugly Number II: Find the nth ugly number, where ugly numbers are positive numbers whose prime factors are limited to 2, 3, and 5.
3. Ugly Number III: Extend the concept of "ugly numbers" to allow any set of prime factors and find the nth "super ugly number" using a given array of primes.

Algorithm:

1. Ugly Number I:
   • Iteratively divide the number by 2, 3, and 5 as long as it is divisible.
   • If the resulting number is 1, return true; otherwise, return false.
2. Ugly Number II:
   • Use dynamic programming to generate the sequence of ugly numbers.
   • Maintain pointers for multiples of 2, 3, and 5 and calculate the minimum value at each step.
   • Store the result in an array and return the nth element.
3. Ugly Number III:
   • Use a min-heap (priority queue) to efficiently find the next ugly number.
   • Deduplicate elements using the heap and track indices of factors for each prime.
   • Return the nth element from the sequence.

Complexity:

Ugly Number I:

• Time Complexity: O(log(num))
• Space Complexity: O(1)

Ugly Number II:

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

Ugly Number III:

• Time Complexity: O(n * log(k)), where k is the number of primes.
• Space Complexity: O(k + n)

Java Implementation:

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

// Ugly Number II
public int nthUglyNumber(int n) {
    int[] ugly = new int[n];
    ugly[0] = 1;
    int index2 = 1, index3 = 1, index5 = 1;
    int next2 = 2, next3 = 3, next5 = 5;

    for (int i = 1; i < n; i++) {
        int min = Math.min(next2, Math.min(next3, next5));
        ugly[i] = min;

        if (next2 == min) next2 = 2 * ugly[index2++];
        if (next3 == min) next3 = 3 * ugly[index3++];
        if (next5 == min) next5 = 5 * ugly[index5++];
    }

    return ugly[n - 1];
}

// Ugly Number III
public int nthSuperUglyNumber(int n, int[] primes) {
    int[] ugly = new int[n];
    ugly[0] = 1;
    PriorityQueue heap = new PriorityQueue<>();

    for (int prime : primes)
        heap.add(new Element(prime, prime, 0));

    for (int i = 1; i < n; i++) {
        ugly[i] = heap.peek().val;

        while (heap.peek().val == ugly[i]) {
            Element nxt = heap.poll();
            heap.add(new Element(nxt.prime * ugly[nxt.idx], nxt.prime, nxt.idx + 1));
        }
    }

    return ugly[n - 1];
}

class Element implements Comparable {
    int val, prime, idx;

    public Element(int val, int prime, int idx) {
        this.val = val;
        this.prime = prime;
        this.idx = idx;
    }

    @Override
    public int compareTo(Element that) {
        return this.val - that.val;
    }
}