# 313. Super Ugly Number

## Description

A super ugly number is a positive integer whose prime factors are in the array primes.

Given an integer n and an array of integers primes, return the nth super ugly number.

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

Example 1:

Input: n = 12, primes = [2,7,13,19]
Output: 32
Explanation: [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].


Example 2:

Input: n = 1, primes = [2,3,5]
Output: 1
Explanation: 1 has no prime factors, therefore all of its prime factors are in the array primes = [2,3,5].


Constraints:

• 1 <= n <= 105
• 1 <= primes.length <= 100
• 2 <= primes[i] <= 1000
• primes[i] is guaranteed to be a prime number.
• All the values of primes are unique and sorted in ascending order.

## Solutions

Solution 1: Priority Queue (Min Heap)

We use a priority queue (min heap) to maintain all possible super ugly numbers, initially putting $1$ into the queue.

Each time we take the smallest super ugly number $x$ from the queue, multiply $x$ by each number in the array primes, and put the product into the queue. Repeat the above operation $n$ times to get the $n$th super ugly number.

Since the problem guarantees that the $n$th super ugly number is within the range of a 32-bit signed integer, before we put the product into the queue, we can first check whether the product exceeds $2^{31} - 1$. If it does, there is no need to put the product into the queue. In addition, the Euler sieve can be used for optimization.

The time complexity is $O(n \times m \times \log (n \times m))$, and the space complexity is $O(n \times m)$. Where $m$ and $n$ are the length of the array primes and the given integer $n$ respectively.

• class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
PriorityQueue<Integer> q = new PriorityQueue<>();
q.offer(1);
int x = 0;
while (n-- > 0) {
x = q.poll();
while (!q.isEmpty() && q.peek() == x) {
q.poll();
}
for (int k : primes) {
if (k <= Integer.MAX_VALUE / x) {
q.offer(k * x);
}
if (x % k == 0) {
break;
}
}
}
return x;
}
}

• class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
priority_queue<int, vector<int>, greater<int>> q;
q.push(1);
int x = 0;
while (n--) {
x = q.top();
q.pop();
for (int& k : primes) {
if (x <= INT_MAX / k) {
q.push(k * x);
}
if (x % k == 0) {
break;
}
}
}
return x;
}
};

• '''
The time complexity of the provided code is O(n * k * log(n))
* where n is the input parameter n.
* where k is the number of prime numbers in the input list

For a single outer for loop iteration
* Popping the smallest element from the heap using heappop(), which takes O(log(n)) time complexity.
* Pushing the new number into the heap using heappush(), which takes O(log(n)) time complexity.
* Therefore, the overall time complexity of the loop is O(k * log(n)), where k is the number of prime numbers in the input list.

Since the loop runs for n iterations and each iteration has a time complexity of O(k * log(n)), the total time complexity of the code is O(n * k * log(n)).

The space complexity of the code is O(n) due to the heap and the hash table
* where n is the input parameter n.
'''

from heapq import heappush, heappop

class Solution:
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
h = [1] # heap
vis = {1} # hashtable to de-dup
ans = 1 # initiator
for _ in range(n):
ans = heappop(h)
for v in primes:
nxt = ans * v
if nxt not in vis:
heappush(h, nxt)
return ans

############

'''
>>> a = {x:x+1 for x in range(10)}
>>> a
{0: 1, 1: 2, 2: 3, 3: 4, 4: 5, 5: 6, 6: 7, 7: 8, 8: 9, 9: 10}
>>> a.items()
[(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9), (9, 10)]
>>> a.values()
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> a.keys()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

>>> float("-inf") == -math.inf
True
'''
class Solution:
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
if n <= 0 or primes is None:
return 0

nums = [1]
index = [0] * len(primes)

while len(nums) < n:
minv = float('inf')
for i in range(len(primes)):
minv = min(minv, primes[i] * nums[index[i]])
nums.append(minv)

for i in range(len(primes)):
if primes[i] * nums[index[i]] == minv:
index[i] += 1

return nums[-1]

if __name__ == '__main__':
# if no de-dup, result will be:
#           [1, 2, 4, 7, 8, 13, 14, 14, 16, 19, 26, 26]
# corret:   [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]
print(Solution().nthSuperUglyNumber(12, [2,7,13,19]))

#############

class Solution: # not that good, just for reference
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
q = [1]
x = 0
mx_int = (1 << 31) - 1
for _ in range(n):
x = heappop(q)
for k in primes:
if x <= mx_int // k: # make sure not overflow int type
heappush(q, k * x)
if x % k == 0: # to avoid duplicates, eg [2,3,5], when x is 6
break
# print(x)
# print(list(q))
return x

'''
primes = [2,3,5]
n = 10
result should be: 12
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]

for the print enabled, I got:

1
[2, 3, 5]
2
[3, 5, 4] ==> heappop got 3, 3%3==0 so still added 3*3=9, but not added 3*5=15
3
[4, 5, 6, 9]
4
[5, 8, 6, 9]
5
[6, 8, 9, 10, 15, 25]
6
[8, 10, 9, 25, 15, 12]
8
[9, 10, 12, 25, 15, 16]
9
[10, 15, 12, 25, 16, 18, 27]
10
[12, 15, 18, 25, 16, 27, 20]
12
[15, 16, 18, 25, 20, 27, 24]
'''


• func nthSuperUglyNumber(n int, primes []int) (x int) {
q := hp{[]int{1} }
for n > 0 {
n--
x = heap.Pop(&q).(int)
for _, k := range primes {
if x <= math.MaxInt32/k {
heap.Push(&q, k*x)
}
if x%k == 0 {
break
}
}
}
return
}

type hp struct{ sort.IntSlice }

func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}