NUHMAN.com

Introduction

LeetCode 313: Super Ugly Number asks us to find the Nth super ugly number. A super ugly number is a number whose prime factors are limited to a given set of primes. The problem provides a list of primes, and you are tasked with finding the Nth super ugly number, where each super ugly number is formed by multiplying the primes in the list together.

This problem is an extension of the classic Ugly Number problem, where we limit the prime factors to a specified set and generate super ugly numbers in ascending order. To solve this problem efficiently, we can utilize a min-heap (priority queue) and dynamic programming.

Problem Statement

A super ugly number is a number whose prime factors are from the given list of primes primes. For example, if primes = [2, 7, 13, 19], then the super ugly numbers are the numbers whose only prime factors are from this list.

Given a list of primes and an integer n, return the Nth super ugly number.

Note:

• The first super ugly number is 1.
• The next super ugly number is the smallest possible number that can be formed by multiplying one or more primes from the list.

Example

python

# Example 1
Input: n = 12, primes = [2, 7, 13, 19]
Output: 32
Explanation: The first 12 super ugly numbers are:
[1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]

# Example 2
Input: n = 1, primes = [2, 3, 5]
Output: 1

Step-by-Step Solution

🧠 Intuition

The problem is to find the Nth super ugly number where the number is generated from the given primes, using only those primes as factors. The naive approach of iterating through all numbers is inefficient, especially for large n. Instead, we can generate the super ugly numbers in ascending order using a min-heap (priority queue) and dynamic programming.

✅ Approach

1. Min-Heap Initialization:
2. We start by initializing a min-heap with the first super ugly number, which is always 1. The min-heap will help us efficiently get the next smallest super ugly number.
3. Generate Super Ugly Numbers:
4. The idea is to repeatedly extract the smallest number from the heap, and for each prime in the list of primes, multiply the smallest number by the prime and insert the product back into the heap. This way, we always get the smallest super ugly number in each iteration.
5. Avoid Duplicates:
6. To avoid inserting duplicate numbers, we maintain a set of already seen numbers. This ensures that each super ugly number is inserted only once into the heap.
7. Repeat Until Nth Number:
8. We repeat the above process until we've extracted the Nth super ugly number from the heap.

✅ Python Code

python

import heapq

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: list[int]) -> int:
        # Min-heap to store the next super ugly number
        heap = []
        # Initialize the heap with the prime numbers
        heapq.heappush(heap, 1)
        
        # Set to track seen numbers and avoid duplicates
        seen = {1}
        
        # The current super ugly number
        ugly_number = 1
        
        for _ in range(n):
            # Extract the smallest super ugly number from the heap
            ugly_number = heapq.heappop(heap)
            
            # For each prime, generate a new super ugly number and push it to the heap
            for prime in primes:
                new_ugly = ugly_number * prime
                if new_ugly not in seen:
                    seen.add(new_ugly)
                    heapq.heappush(heap, new_ugly)
        
        return ugly_number

Explanation of the Code

1. Heap Initialization:
2. We initialize the min-heap with the value 1, as the first super ugly number is always 1. This allows us to start the process of generating the super ugly numbers from the smallest possible value.
3. Set for Tracking Seen Numbers:
4. We maintain a seen set to track which numbers have already been added to the heap. This prevents duplicates from being added to the heap.
5. Main Loop:
6. We run a loop n times to extract the smallest super ugly number. For each extracted number, we generate new super ugly numbers by multiplying it by each prime in the primes list, and if the product hasn’t been seen before, we add it to the heap and the seen set.
7. Return the Nth Super Ugly Number:
8. The loop continues until we extract the Nth super ugly number, which is then returned.

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(n * k log n)Space ComplexityO(n)

• Time Complexity:
• The loop runs n times, and in each iteration, we perform k operations (one for each prime in the list). For each prime, we insert a new number into the heap, and the heap insertion operation takes O(log n) time. Therefore, the time complexity is O(n * k log n), where n is the number of super ugly numbers to find and k is the number of primes.
• Space Complexity:
• The space complexity is O(n) because the heap will store up to n super ugly numbers at any given time, and the seen set also stores n numbers.

🔍 Edge Cases

1. n = 1:
2. If n = 1, the answer is simply 1 because the first super ugly number is always 1.
3. Single Prime in Primes List:
4. If the primes list contains only one prime (e.g., [2]), the super ugly numbers will be powers of 2, such as [1, 2, 4, 8, 16, ...].
5. Primes List with Multiple Primes:
6. When there are multiple primes, the algorithm will generate the super ugly numbers by multiplying different combinations of these primes.
7. Large n:
8. The algorithm should handle large n efficiently because the heap allows us to maintain the smallest numbers in sorted order without having to generate all numbers explicitly.

✅ Conclusion

LeetCode 313: Super Ugly Number is a problem that requires finding the Nth super ugly number by considering only certain primes as factors. The solution is efficiently implemented using a min-heap and a set to avoid duplicates. This approach allows us to generate the sequence of super ugly numbers in ascending order without directly iterating over all numbers.