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 =  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]