Super Ugly Number - Leetcode Solution

The Super Ugly Number problem on LeetCode asks us to find the nth super ugly number given a set of prime numbers. A super ugly number is defined as a positive integer whose prime factors are in the given set.

We will start by defining a function called superUglyNumber that takes two inputs - n (the nth super ugly number we need to find) and primes (the set of prime numbers whose multiples we need to consider).

We will begin by initializing a list called ugly with the first super ugly number i.e., 1.

We will also initialize a dictionary called factors where the keys are the prime numbers and the values are indices that we will use to keep track of the multiples of these prime numbers in the ugly list.

Next, we will define a loop that runs n-1 times (since we have already added the first super ugly number to the list). In each iteration, we will find the next super ugly number and add it to the ugly list.

To find the next super ugly number, we will first create a list called candidates that contains all possible multiples of the prime numbers in the given set whose indices are stored in the factors dictionary.

We will then find the minimum number in the candidates list and add it to the ugly list. We will also update the corresponding index of this prime number in the factors dictionary by adding 1 to it. This is because the next multiple of this prime number will be at the index given by the updated value in the factors dictionary.

Finally, we will return the last element of the ugly list as the nth super ugly number.

The time complexity of this solution is O(n * k), where n is the nth super ugly number and k is the number of prime numbers in the given set. The space complexity is O(n * k) as well since we are storing the ugly list and the factors dictionary.

Here's the Python code for the same:

def superUglyNumber(n, primes):
    ugly = [1]
    factors = {p: 0 for p in primes}
    
    for i in range(n-1):
        candidates = [ugly[factors[p]] * p for p in primes]
        next_ugly = min(candidates)
        ugly.append(next_ugly)
        
        for p in primes:
            if next_ugly == ugly[factors[p]] * p:
                factors[p] += 1
                
    return ugly[-1]

Example:

n = 12
primes = [2, 7, 13, 19]
print(superUglyNumber(n, primes))

Output:

32

Explanation:

The first 12 super ugly numbers are:

1, 2, 4, 7, 8, 13, 14, 19, 26, 28, 32, 38

The 12th super ugly number is 38.

1