• 37.2%

https://leetcode.com/problems/super-ugly-number

Write a program to find the nth super ugly number.

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

Note:

(1) 1 is a super ugly number for any given primes.

(2) The given numbers in primes are in ascending order.

(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.

(4) The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

https://leetcode.com/problems/super-ugly-number/

Keep k pointers and update them in each iteration. Time complexity is O(kn).

156ms, 44.15%, May.3rd, 2016

https://leetcode.com/discuss/74625/112ms-c-solution-with-explanation

164ms, 35.72%, 83 / 83, May.3rd, 2016

https://leetcode.com/discuss/72878/7-line-consice-o-kn-c-solution

#### python

Solution 1:

540ms, 76.45%, 83 / 83, May.3rd, 2016

https://leetcode.com/discuss/72763/python-generators-on-a-heap

#### java

https://discuss.leetcode.com/topic/34841/java-three-methods-23ms-36-ms-58ms-with-heap-performance-explained

Basic idea is same as ugly number II, new ugly number is generated by multiplying a prime with previous generated ugly number. One catch is need to remove duplicate

Let’s start with the common solution from ugly number II 36 ms, Theoretically O(kN)

If you look at the above solution, it has redundant multiplication can be avoided, and also two for loops can be consolidated into one. This trade-off space for speed. 23 ms, Theoretically O(kN)

Can we do better? Theoretically yes, by keep the one candidates for each prime in a heap, it can improve the theoretical bound to O( log(k)N ), but in reality it’s 58 ms. I think it’s the result of using higher level object instead of primitive. Can be improved by writing an index heap (http://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html)

my code