Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/313.html
313 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.
Example:
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] of size 4.
Note:
1 is a super ugly number for any given primes.
The given numbers in primes are in ascending order.
0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
The nth super ugly number is guaranteed to fit in a 32-bit signed integer.
@tag-array
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; } };
-
class Solution: def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int: q = [1] x = 0 mx = (1 << 31) - 1 for _ in range(n): x = heappop(q) for k in primes: if x <= mx // k: heappush(q, k * x) if x % k == 0: break return x ############ ''' >>> 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])) ############# import heapq class Solution(object): def nthSuperUglyNumber(self, n, primes): """ :type n: int :type primes: List[int] :rtype: int """ dp = [0] * (n + 1) dp[1] = 1 heap = [] indexes = [1] * len(primes) for i in range(0, len(primes)): heapq.heappush(heap, (dp[indexes[i]] * primes[i], i)) for i in range(2, n + 1): minV = heap[0][0] dp[i] = minV while heap[0][0] == minV: value, xi = heapq.heappop(heap) indexes[xi] += 1 heapq.heappush(heap, (dp[indexes[xi]] * primes[xi], xi)) return dp[-1]
-
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 }