Super Ugly Number

Super Ugly Number Problem

Problem Description

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.

For example:

• n = 12, primes = [2, 7, 13, 19] => Output: 32. The sequence is [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32].
• n = 1, primes = [2, 3, 5] => Output: 1

Naive Approach

A brute force solution would involve generating all possible numbers and checking if they are super ugly numbers. This is highly inefficient.

Optimal Approach

We can use dynamic programming to solve this problem efficiently. We maintain an array ugly to store the super ugly numbers, and an array pointers to track the index of each prime number in the ugly array. For each index i from 1 to n-1, we find the minimum value among ugly[pointers[j]] * primes[j] for all j and update the ugly array. If a prime number generates the minimum ugly number, its corresponding pointer is incremented. This approach ensures that we only consider the necessary multiplications, and reduces time complexity.

def nthSuperUglyNumber(n, primes):
    ugly = [0] * n
    ugly[0] = 1
    pointers = [0] * len(primes)

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

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

    return ugly[n - 1]

Edge Cases

• n = 1: should return 1.
• primes is empty. (Problem statement guarantees primes.length >= 1.)
• Large values of n that might cause integer overflow (problem statement guarantees a 32-bit signed integer)

Time and Space Complexity

• Time Complexity: O(n * k), where n is the nth super ugly number to find and k is the number of primes.
• Space Complexity: O(n + k), where n is for the ugly array and k is for the pointers array.