Ugly Number II

Leetcode Problem:

• Ugly Number II

Summary

• Find the nth ugly number which is a positive integer whose prime factors are limited to 2, 3, and 5.

Approach

• Use a min-heap to store the ugly numbers and a map to keep track of processed numbers
• The algorithm starts by pushing 1 into the heap and then repeatedly pops the smallest number, multiplies it by 2, 3, and 5, and pushes the results back into the heap until the nth ugly number is found.

Complexity

• O(n log n) due to the heap operations

Explain

• The solution uses a min-heap to efficiently store and retrieve the ugly numbers
• The `push` operation is used to add a new ugly number to the heap, and the `pop` operation is used to remove the smallest ugly number from the heap
• The algorithm also uses a map to keep track of processed numbers to avoid duplicates
• The time complexity of the solution is O(n log n) due to the heap operations, where n is the input number.

Solution Code:

struct _heap{
    long long arr[10000];
    int size;
    _heap(){
        size = 1;
    }
    void push(long long a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && arr[idx] < arr[idx/2]){
            long long t = arr[idx];
            arr[idx] = arr[idx/2];
            arr[idx/2] = t;
            idx/=2;
        }
    }
    long long pop(){
        long long ret = arr[1];
        arr[1] = arr[--size];
        int i = 1;
        while(true){
            int j = i * 2;
            if (j >= size) break;
            if (j + 1 < size && arr[j] > arr[j+1]){
                j++;
            }
            if(arr[j] < arr[i]){
                long long t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
                i = j;
            }
            else {
                break;
            }
        }
        return ret;
    }
};

class Solution {
public:
    _heap pq;
    unordered_map processed;
    int nthUglyNumber(int n) {
        if (n == 1) return 1;
        int idx = 1;
        pq.push(1); 
        long long num = 1;      
        while(n--){
            num = pq.pop();
            if (processed[num]) {
                n++;
                continue;
            }
            processed[num] = true;
            pq.push(num*2);
            pq.push(num*3);
            pq.push(num*5);
        }
        return num;
    }
};