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.
-
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 }