Introduction

In this blog post, we will explore how to solve the LeetCode problem "313" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

A super ugly number is a positive integer whose prime factors are in the array primes. Given an integer n and an array of integers primes, return the nth super ugly number. The nth super ugly number is guaranteed to fit in a 32-bit signed integer. Example 1: Input: n = 12, primes = [2,7,13,19] Output: 32 Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19]. Example 2: Input: n = 1, primes = [2,3,5] Output: 1 Explanation: 1 has no prime factors, therefore all of its prime factors are in the array primes = [2,3,5]. Constraints: 1 <= n <= 105 1 <= primes.length <= 100 2 <= primes[i] <= 1000 primes[i] is guaranteed to be a prime number. All the values of primes are unique and sorted in ascending order.

Explanation

Here's the breakdown of the solution:

• Dynamic Programming: We build an array ugly to store the super ugly numbers in increasing order. ugly[i] will represent the i-th super ugly number.
• Pointers for Primes: We maintain an array pointers where pointers[j] stores the index of the super ugly number that should be multiplied by primes[j] to generate the next potential super ugly number.

• Finding the Minimum: In each iteration, we find the smallest number generated by multiplying each prime with its corresponding super ugly number (indicated by the pointers array).

• Runtime: O(n * k), where n is the desired nth ugly number and k is the number of primes. Storage: O(n + k)

Code

    def nthSuperUglyNumber(n: int, primes: list[int]) -> int:
    """
    Finds the nth super ugly number.

    Args:
        n: The desired nth ugly number.
        primes: A list of prime factors.

    Returns:
        The nth super ugly number.
    """

    ugly = [0] * n
    ugly[0] = 1
    pointers = [0] * len(primes)

    for i in range(1, n):
        next_ugly = float('inf')
        for j in range(len(primes)):
            next_ugly = min(next_ugly, primes[j] * ugly[pointers[j]])

        ugly[i] = next_ugly

        for j in range(len(primes)):
            if primes[j] * ugly[pointers[j]] == next_ugly:
                pointers[j] += 1

    return ugly[n - 1]