LeetCode 313: Super Ugly Number Solution in Python – A Step-by-Step Guide

What Is LeetCode 313: Super Ugly Number?

In LeetCode 313: Super Ugly Number, you’re given a list of prime numbers primes and an integer n. Your task is to find the nth “super ugly number”—a sequence where each number is a product of earlier numbers (starting with 1) and the given primes. For example, with primes = [2, 7, 13, 19] and n = 12, the sequence starts [1, 2, 4, 7, 8, 13, 14, 19, 26, 28, 32, 49], and the 12th is 49. This problem builds on LeetCode 264: Ugly Number II, generalizing it to any set of primes.

Problem Statement

• Input: Integer n and array primes of distinct prime numbers.
• Output: An integer—the nth super ugly number.
• Rules:
• Sequence starts with 1.
• Each subsequent number is a prime from primes times an earlier number.
• Numbers must be in ascending order.

Constraints

• 1 <= n <= 10⁵
• 1 <= primes.length <= 100
• 2 <= primes[i] <= 1000
• primes[i] are distinct primes.

Examples

• Input: n = 12, primes = [2,7,13,19]
• Output: 49 (Sequence: [1,2,4,7,8,13,14,19,26,28,32,49])
• Input: n = 1, primes = [2,3,5]
• Output: 1 (First number is 1)
• Input: n = 5, primes = [2,3]
• Output: 6 (Sequence: [1,2,3,4,6])

Understanding the Problem: Finding the nth Super Ugly Number

To solve LeetCode 313: Super Ugly Number in Python, we need to generate the super ugly number sequence up to the nth term efficiently. A naive approach—generating all possible products and sorting—would be impractical due to the size of n. Instead, we’ll use:

• Best Solution (Heap-Based): O(n * k * log k) time, O(k) space—where k is len(primes)—fast and scalable.
• Alternative Solution (Dynamic Programming): O(n * k) time, O(n) space—clear but memory-heavy.

Let’s start with the heap-based solution, explained in a beginner-friendly way.

Best Solution: Heap-Based Approach

Why This Is the Best Solution

The heap-based approach is the top choice for LeetCode 313 because it’s efficient—O(n * k * log k) time, O(k) space—and elegantly handles the sequence generation. It uses a min-heap to always pick the smallest next super ugly number, avoiding duplicates with a set. It’s like a treasure map that always points to the next gem—smart and resource-light!

How It Works

Think of this as a priority queue game:

• Step 1: Initialize:
• Start with 1 in the sequence.
• Use a heap to track next candidates (prime * smallest number).
• Step 2: Generate Sequence:
• Pop smallest from heap, add to sequence.
• Push next multiples for each prime, skip duplicates.
• Step 3: Repeat:
• Continue until nth number is found.
• Step 4: Why It Works:
• Heap ensures ascending order.
• Set prevents duplicates efficiently.

It’s like picking the smallest treasure each step!

Step-by-Step Example

Example: n = 5, primes = [2,3]

• Init: Sequence = [1], Heap = [(2,0,2), (3,0,3)], Seen = {1}
• Step 1: Pop 2, Sequence = [1,2], Heap = [(3,0,3), (4,1,2)], Seen = {1,2}
• Step 2: Pop 3, Sequence = [1,2,3], Heap = [(4,1,2), (6,2,3)], Seen = {1,2,3}
• Step 3: Pop 4, Sequence = [1,2,3,4], Heap = [(6,2,3), (8,3,2)], Seen = {1,2,3,4}
• Step 4: Pop 6, Sequence = [1,2,3,4,6], Heap = [(8,3,2), (9,4,3)]
• Result: 6 (5th number).

Code with Detailed Line-by-Line Explanation

Copy codeimport heapq

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        if n == 1:
            return 1

        # Min-heap: (value, index in sequence, prime)
        heap = [(prime, 0, prime) for prime in primes]
        heapq.heapify(heap)
        seen = {1}  # Track numbers to avoid duplicates
        ugly = [1]  # Sequence starts with 1

        # Generate n numbers
        while len(ugly) < n:
            val, idx, prime = heapq.heappop(heap)
            next_val = val
            if next_val not in seen:
                seen.add(next_val)
                ugly.append(next_val)
                # Push next multiple
                heapq.heappush(heap, (prime * ugly[idx + 1], idx + 1, prime))

        return ugly[-1]

• Lines 5-6: Handle base case.
• Line 9: Heap starts with each prime * 1.
• Lines 10-11: Initialize heap and seen set.
• Lines 14-20: Loop:
• Pop smallest candidate.
• If new, add to sequence, push next multiple.
• Line 22: Return nth number.
• Time Complexity: O(n * k * log k)—heap operations.
• Space Complexity: O(k)—heap size.

This is like a number-hunting machine—swift and precise!

Alternative Solution: Dynamic Programming with Pointers

Why an Alternative Approach?

The DP approach uses an array and pointers—O(n * k) time, O(n) space. It’s more straightforward, tracking the next multiple for each prime explicitly, but uses more memory. It’s like a ledger of ugly numbers—clear and systematic!

How It Works

Track progress with pointers:

• Step 1: Initialize sequence with 1, pointers for each prime.
• Step 2: For each position:
• Find min of prime * next ugly number.
• Update pointers for used primes.
• Step 3: Build up to n.

Step-by-Step Example

Example: n = 4, primes = [2,3]

• Init: ugly = [1], pointers = [0, 0]
• Step 1: Min(2*1, 3*1) = 2, ugly = [1,2], pointers = [1, 0]
• Step 2: Min(2*2, 3*1) = 3, ugly = [1,2,3], pointers = [1, 1]
• Step 3: Min(2*2, 3*2) = 4, ugly = [1,2,3,4], pointers = [2, 1]
• Result: 4.

Code for DP Approach

Copy codeclass Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        if n == 1:
            return 1

        k = len(primes)
        ugly = [1] * n
        pointers = [0] * k
        next_vals = primes.copy()  # Next candidate for each prime

        for i in range(1, n):
            min_val = min(next_vals)
            ugly[i] = min_val
            for j in range(k):
                if next_vals[j] == min_val:
                    pointers[j] += 1
                    next_vals[j] = primes[j] * ugly[pointers[j]]

        return ugly[n-1]

• Time Complexity: O(n * k)—linear scan per number.
• Space Complexity: O(n)—sequence storage.

It’s a steady number builder!

Comparing the Two Solutions

• Heap-Based (Best):
• Pros: O(n * k * log k) time, O(k) space, scalable.
• Cons: Heap logic less intuitive.
• DP (Alternative):
• Pros: O(n * k) time, O(n) space, simpler concept.
• Cons: More memory.

Heap wins for space efficiency.

Additional Examples and Edge Cases

• n=3, [2]: 4 ([1,2,4]).
• n=2, [5]: 5 ([1,5]).
• n=1, [2,3]: 1.

Both handle these well.

Complexity Breakdown

• Heap-Based: Time O(n * k * log k), Space O(k).
• DP: Time O(n * k), Space O(n).

Heap is leaner; DP is faster in practice for small k.

Key Takeaways

• Heap-Based: Priority wins—elegant!
• DP: Pointers rule—clear!
• Python: Heaps and lists shine—see [Python Basics](/python/basics).
• Numbers: Primes make it fun.

Final Thoughts: Hunt the Ugly Number

LeetCode 313: Super Ugly Number in Python is a mathematical adventure. The heap-based solution offers efficiency and flair, while DP provides a solid foundation. Want more number challenges? Try LeetCode 264: Ugly Number II or LeetCode 204: Count Primes. Ready to hunt? Head to Solve LeetCode 313 on LeetCode and find that nth treasure today!