Welcome to Subscribe On Youtube
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 <= 1051 <= primes.length <= 1002 <= primes[i] <= 1000primes[i]is guaranteed to be a prime number.- All the values of
primesare 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.
Solution 2
This implementation uses breadth-first search. It traverses the relevant values and updates its state as each value is processed. The auxiliary container determines which pending state is processed next. After all required states have been considered, the maintained result is returned.
-
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: vis.add(nxt) 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 } // Solution 2 type Ugly struct{ value, prime, index int } type Queue []Ugly func (u Queue) Len() int { return len(u) } func (u Queue) Swap(i, j int) { u[i], u[j] = u[j], u[i] } func (u Queue) Less(i, j int) bool { return u[i].value < u[j].value } func (u *Queue) Push(v any) { *u = append(*u, v.(Ugly)) } func (u *Queue) Pop() any { old, x := *u, (*u)[len(*u)-1] *u = old[:len(old)-1] return x } func nthSuperUglyNumber(n int, primes []int) int { ugly, pq, p := make([]int, n+1), &Queue{}, 2 ugly[1] = 1 heap.Init(pq) for _, v := range primes { heap.Push(pq, Ugly{value: v, prime: v, index: 2}) } for p <= n { top := heap.Pop(pq).(Ugly) if ugly[p-1] != top.value { ugly[p], p = top.value, p+1 } top.value, top.index = ugly[top.index]*top.prime, top.index+1 heap.Push(pq, top) } return ugly[n] }