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

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
    }
    

All Problems

All Solutions