algoadvance

Leetcode 264. Ugly Number II

Problem Statement

Write a program to find the nth ugly number.

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Clarifying Questions

1. Input: What is the range of n?
   • The input n is a positive integer and can be as large as 1690.
2. Output: Should we return the nth ugly number as an integer?
   • Yes, return the nth ugly number.

Strategy

To find the nth ugly number, we can use a dynamic programming approach combined with a min-heap (priority queue).

Steps:

1. Initialization:
   • Initialize a minimum heap and insert the first ugly number 1 along with its multiples by 2, 3, and 5.
   • Use a set to avoid duplicates.
2. Iterate:
   • Extract the minimum number from the heap.
   • For each extracted number, generate its multiples (current_number * 2, current_number * 3, current_number * 5) and insert them back into the heap if they are not already present.
   • Track the count of numbers extracted until we reach the nth ugly number.
3. Return:
   • Return the nth number when the count matches n.

Code

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

int nthUglyNumber(int n) {
    if (n <= 0) return 0; // Assuming we handle invalid inputs with a default return value.
    
    std::priority_queue<long, std::vector<long>, std::greater<long>> minHeap;
    std::unordered_set<long> seen; // To avoid duplicates

    // Initialize with the first ugly number
    minHeap.push(1);
    seen.insert(1);

    long currentUgly = 1;

    // Factors for computing ugly numbers
    std::vector<int> factors = {2, 3, 5};

    // We need to find the nth ugly number
    for (int i = 1; i <= n; ++i) {
        currentUgly = minHeap.top();
        minHeap.pop();

        for (int factor : factors) {
            long newUgly = currentUgly * factor;
            if (seen.find(newUgly) == seen.end()) {
                minHeap.push(newUgly);
                seen.insert(newUgly);
            }
        }
    }

    return static_cast<int>(currentUgly);
}

int main() {
    int n = 10; // Example usage
    std::cout << "The " << n << "th ugly number is: " << nthUglyNumber(n) << std::endl;
    return 0;
}

Time Complexity

• Heap Operations: Inserting and extracting the minimum element from the heap takes O(log k), where k is the size of the heap.
• Overall Complexity: Given that each number generates three new candidate numbers and we perform this up to n times, the overall complexity is O(n log n).

Space Complexity

• The space complexity is influenced by the space needed for the heap and the hash set. In the worst case, this is proportional to the number of distinct ugly numbers less than the nth ugly number:
  • Space Complexity: O(n)

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?