Dare2Solve
Given an integer n
and a list of prime numbers, primes
, the task is to find the n
-th super ugly number. A super ugly number is a positive integer whose only prime factors are listed in primes
. The sequence of super ugly numbers is defined such that the i
-th element is the smallest number whose prime factors are only from the given list.
To determine the n
-th super ugly number efficiently, we need a strategy that avoids generating all possible ugly numbers up to n
, which would be infeasible for large values. Instead, we use a priority queue to dynamically track and generate the sequence of ugly numbers in a sorted order.
Priority Queue Initialization:
Generate Super Ugly Numbers:
1
(the first super ugly number) and iteratively generate new super ugly numbers by multiplying the smallest number in the priority queue with each prime from the primes
list.Populate Output:
Return Result:
n
-th super ugly number is found, which will be the result.n
times.class Solution {
public:
struct Compare {
bool operator()(const vector<long>& a, const vector<long>& b) {
return a[0] > b[0];
}
};
int nthSuperUglyNumber(int n, vector<int>& primes) {
priority_queue<vector<long>, vector<vector<long>>, Compare> minPQ;
// Initialize the priority queue with the first prime multiples
for (int prime : primes) {
minPQ.push({prime, 0, prime}); // {value, index in output, prime factor}
}
vector<long> output(1, 1); // The first super ugly number is always 1
while (output.size() < n) {
vector<long> current = minPQ.top();
minPQ.pop();
long value = current[0], idx = current[1], prime = current[2];
// Avoid adding duplicate values to the output array
if (value != output.back()) {
output.push_back(value);
}
// Generate the next multiple of the current prime
minPQ.push({output[idx + 1] * prime, idx + 1, prime});
}
return output[n - 1];
}
};
class Solution:
def nthSuperUglyNumber(self, n: int, primes: list[int]) -> int:
minPQ = []
# Initialize the priority queue with the first prime multiples
for prime in primes:
heapq.heappush(minPQ, (prime, 0, prime)) # (value, index in output, prime factor)
output = [1] # The first super ugly number is always 1
while len(output) < n:
value, idx, prime = heapq.heappop(minPQ)
# Avoid adding duplicate values to the output list
if value != output[-1]:
output.append(value)
# Generate the next multiple of the current prime
heapq.heappush(minPQ, (output[idx + 1] * prime, idx + 1, prime))
return output[n - 1]
class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
// Priority queue to get the smallest current number
PriorityQueue<long[]> minPQ = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
// Initialize the priority queue with the first prime multiples
for (int prime : primes) {
minPQ.offer(new long[] {prime, 0, prime}); // [value, index in output, prime factor]
}
// Array to store the ugly numbers
long[] output = new long[n];
output[0] = 1; // The first super ugly number is always 1
// Populate the output array
for (int i = 1; i < n; i++) {
long[] current = minPQ.poll();
long value = current[0];
int idx = (int)current[1];
long prime = current[2];
// Avoid adding duplicate values to the output array
if (value != output[i - 1]) {
output[i] = value;
} else {
i--; // If duplicate, redo this index
}
// Generate the next multiple of the current prime
minPQ.offer(new long[] {output[idx + 1] * prime, idx + 1, prime});
}
return (int)output[n - 1];
}
}
/**
* @param {number} n
* @param {number[]} primes
* @return {number}
*/
var nthSuperUglyNumber = function (n, primes) {
const minPQ = new PriorityQueue({ compare: (a, b) => a[0] - b[0] });
// Initialize the priority queue with the first prime multiples
for (const prime of primes) {
minPQ.enqueue([prime, 0, prime]); // [value, index in output, prime factor]
}
const output = [1]; // The first super ugly number is always 1
while (output.length < n) {
const [value, idx, prime] = minPQ.dequeue();
// Avoid adding duplicate values to the output array
if (value !== output[output.length - 1]) {
output.push(value);
}
// Generate the next multiple of the current prime
minPQ.enqueue([output[idx + 1] * prime, idx + 1, prime]);
}
return output[n - 1];
};