Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/313.html
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.
Algorithm
Use an idx array to save the current position, and then we take a number from each prime-sub-chain, find the minimum value, and update the corresponding position of the idx array.
Note that there may be more than one minimum value.
Then update the positions of all the minimum values.
Code
-
import java.util.ArrayList; import java.util.List; public class Super_Ugly_Number { public static void main(String[] args) { Super_Ugly_Number out = new Super_Ugly_Number(); Solution s = out.new Solution(); System.out.println(s.nthSuperUglyNumber(12, new int[]{2,7,13,19})); } class Solution { public int nthSuperUglyNumber(int n, int[] primes) { if (n <= 0 || primes == null) { return 0; } List<Integer> nums = new ArrayList<>(); nums.add(1); int[] index = new int[primes.length]; // @note: idx[i] meaning for primes[i], its count to * while (nums.size() < n) { int minv = Integer.MAX_VALUE; for (int i = 0; i < primes.length; i++) { minv = Math.min(minv, primes[i] * nums.get(index[i])); } nums.add(minv); for (int i = 0; i < primes.length; i++) { if (primes[i] * nums.get(index[i]) == minv) { index[i]++; } } } return nums.get(nums.size() - 1); } } } ############ 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 interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) } func (h *hp) Pop() interface{} { a := h.IntSlice v := a[len(a)-1] h.IntSlice = a[:len(a)-1] return v }