LeetCode Q313: 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.

Solution:

I first try to use heap like the one I used in uglu number II. However, I got a TLE due to exploration of heap size when n is a large number. 

I checked the LeetCode discussion, and find following solution in which we track the smallest number generated by each prime. We save such information in an array. To avoid duplicates, Add another for loop to rule out all duplicates.

One could even use a heap to speed up the search for the next available number. However, according to discussion on LeetCode, in practice, it is slower than above solution.

Round 2 solution: