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
}

313 - Super Ugly Number

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions