Super Ugly Number

Write a program to find the nthsuper ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime listprimesof sizek. For example,[1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]is the sequence of the first 12 super ugly numbers givenprimes=[2, 7, 13, 19]of size 4.

Note:
(1)1is a super ugly number for any givenprimes.
(2) The given numbers inprimesare in ascending order.
(3) 0 <k≤ 100, 0 <n≤ 106, 0 <primes[i]< 1000.
(4) The nthsuper ugly number is guaranteed to fit in a 32-bit signed integer.

Solution:

Time Complexity: O( n * k )

Extra Space: O(k)

Same idea as the second approach of ugly number II,

use indices to indicate which prime number can be multiplied to nums[i] to generate the minVal in iteration. Iterate on the prime number frequency record.

class Solution(object):
    def nthSuperUglyNumber(self, n, primes):
        """
        :type n: int
        :type primes: List[int]
        :rtype: int
        """
        # initiating all the indices for the primes
        dic = {}     # dictionary stores prime number as key, its index as value
        for prime in primes:
            dic[prime] = 0

        nums = [1]
        k = len(primes)
        for i in range(n):
            minVal = sys.maxint

            # O(k) operation
            for primeKey in primes:
                if minVal > nums[dic[primeKey]] * primeKey:
                    minVal = nums[dic[primeKey]] * primeKey

            nums.append(minVal)

            # increase the index for the primekey that can generate the same minVal result
            for primeKey in primes:
                if minVal == nums[dic[primeKey]] * primeKey:
                    dic[primeKey] += 1

        return nums[n - 1]