Algorithm

Problem Name: 313. Super Ugly Number

Problem Link: https://leetcode.com/problems/super-ugly-number/
 

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.

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int>dp(n);
        dp[0] = 1;
        vector<int>p(primes.size());
        for(int i = 1; i  <  n; i++){
            dp[i] = INT_MAX;
            for(int j = 0; j  <  p.size(); j++) dp[i] = min(dp[i], dp[p[j]] * primes[j]);
            for(int j = 0; j  <  p.size(); j++) if(dp[p[j]] * primes[j] == dp[i]) p[j]++;
        }
        return dp[n - 1];
    }
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
n = 12, primes = [2,7,13,19]

Output

x
–
+
cmd
32

#2 Code Example with Java Programming

Code - Java Programming


class Solution {
    public static int nthSuperUglyNumber(int n, int[] primes) {
        int[] arr = new int[n+1];
        arr[0] = 1;

        int[] counter = new int[primes.length];

        for (int i=1; i < n; i++) {
            int temp = Integer.MAX_VALUE;
            int idx = -1;

            for (int j=0; j < primes.length; j++) {
                if (primes[j]*arr[counter[j]] < temp) {
                    temp = primes[j]*arr[counter[j]];
                    idx = j;
                }
                else if (primes[j]*arr[counter[j]] == temp) {
                    counter[j]++;
                }
            }

            arr[i] = temp;
            counter[idx]++;
        }

        return arr[n-1];
    }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
n = 12, primes = [2,7,13,19]

Output

x
–
+
cmd
32

#3 Code Example with Javascript Programming

Code - Javascript Programming


const nthSuperUglyNumber = function(n, primes) {
  if (n === 1) return 1
  const indexes = new Array(primes.length).fill(0)
  const arr = [1]
  for (let i = 1; i  < = n - 1; i++) {
    arr[i] = +Infinity
    for (let j = 0; j  <  primes.length; j++) {
      arr[i] = Math.min(arr[i], arr[indexes[j]] * primes[j])
    }
    for (let j = 0; j  <  primes.length; j++) {
      if (arr[i] === arr[indexes[j]] * primes[j]) {
        indexes[j]++
      }
    }
  }
  return arr[n - 1]
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
n = 1, primes = [2,3,5]

Output

x
–
+
cmd
1

#4 Code Example with Python Programming

Code - Python Programming


class Solution:
    def nthSuperUglyNumber(self, n, primes):
        arr, heap, used = [1], primes[:], set()
        for i in range(1, n):
            num = heapq.heappop(heap)
            arr.append(num)
            for p in primes:
                if p * num not in used:
                    heapq.heappush(heap, p * num)
                    used.add(p * num)
        return arr[-1]
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
n = 1, primes = [2,3,5]

Output

x
–
+
cmd
1
Advertisements

Demonstration

Previous
#312 Leetcode Burst Balloons Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#315 Leetcode Count of Smaller Numbers After Self Solution in C, C++, Java, JavaScript, Python, C# Leetcode