Last updated on February 9th, 2025 at 07:16 am
Here, we see a Super Ugly Number LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Heap, Math
Companies
Level of Question
Medium
Super Ugly Number LeetCode Solution
Table of Contents
1. Problem Statement
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].
2. Coding Pattern Used in Solution
The coding pattern used in this problem is K-way Merge. This pattern is commonly used when merging multiple sorted lists or streams into a single sorted list. In this case, the algorithm generates the next “super ugly number” by merging multiple streams of numbers, where each stream is generated by multiplying a prime number with previously computed “super ugly numbers.”
3. Code Implementation in Different Languages
3.1 Super Ugly Number C++
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
if (n == 1)
return 1;
int numPrimes = primes.size();
vector<int> primeIndices(numPrimes, 0);
int superUgly[n];
superUgly[0] = 1;
for (int i = 1; i < n; i++) {
long minVal = INT_MAX;
for (int j = 0; j < numPrimes; j++) {
minVal = min(minVal, (long)primes[j] * superUgly[primeIndices[j]]);
}
superUgly[i] = (int)minVal;
for (int j = 0; j < numPrimes; j++) {
if (minVal == (long)primes[j] * superUgly[primeIndices[j]]) {
primeIndices[j]++;
}
}
}
return superUgly[n - 1];
}
};
3.2 Super Ugly Number Java
class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
int[] ugly = new int[n+1];
ugly[0]=1;
int[] pointer = new int[primes.length];
for(int i=1;i<n;i++) {
int min=Integer.MAX_VALUE;
int minIndex = 0;
for(int j=0;j<primes.length;j++) {
if(ugly[pointer[j]]*primes[j]<min) {
min=ugly[pointer[j]]*primes[j];
minIndex = j;
}else if(ugly[pointer[j]]*primes[j]==min) {
pointer[j]++;
}
}
ugly[i]=min;
pointer[minIndex]++;
}
return ugly[n-1];
}
}
3.3 Super Ugly Number JavaScript
var nthSuperUglyNumber = function(n, primes) {
let indeces = [];
let currents = [];
let i, l;
for (i = 0, l = primes.length; i < l; i++) {
indeces[i] = 0;
}
let out = [1];
while (!out[n-1]) {
for (i = 0, l = primes.length; i < l; i++) {
currents[i] = out[indeces[i]] * primes[i];
}
let next = Math.min(...currents);
out.push(next);
for (i = 0, l = primes.length; i < l; i++) {
if (next === out[indeces[i]] * primes[i]) {
indeces[i] = indeces[i] + 1;
}
}
}
return out[n-1];
};
3.4 Super Ugly Number Python
class Solution(object):
def nthSuperUglyNumber(self, n, primes):
uglies = [1]
def gen(prime):
for ugly in uglies:
yield ugly * prime
merged = heapq.merge(*map(gen, primes))
while len(uglies) < n:
ugly = next(merged)
if ugly != uglies[-1]:
uglies.append(ugly)
return uglies[-1]
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n * k) | O(n * k) |
| Java | O(n * k) | O(n * k) |
| JavaScript | O(n * k) | O(n * k) |
| Python | O(n * log k) | O(n * k) |