Dynamic Programming Solution w/ Explaination


  • 0

    Idea is to use an array to keep track of a pointer for each prime number.

    dp[i] = min(prime1 * dp[p1], prime2 * dp[p2] ...)
    

    prime 1 * dp[p1] gives the multiple of prime 1 that is JUST greater than dp[i-1]. We iterate over all primes and test which is the smallest. Then we do a second iteration to increment the all pointers which have primes that match the smallest number. End the loop when our res gets to size of n.

    def nthSuperUglyNumber(self, n, primes):
        k = len(primes)
        # keep a set of pointers for each prime number
        primes_p = [0 for i in range(k)]
        res = [1]
        while len(res) != n:
            # at each iteration, search for the smallest available prime * res[pointer]
            smallest = sys.maxint
            for i in range(k):
                smallest = min(smallest, primes[i] * res[primes_p[i]])
            res.append(smallest)
            for i in range(k):
                if primes[i] * res[primes_p[i]] == smallest:
                    primes_p[i] += 1
        return res[-1]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.