In this guide, you will get 313. Super Ugly Number LeetCode Solution with the best time and space complexity. The solution to Super Ugly Number problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
Complexity Analysis
Time Complexity: O(nk)
Space Complexity: O(k)
313. Super Ugly Number LeetCode Solution in C++
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
const int k = primes.size();
vector<int> indices(k);
vector<int> uglyNums{1};
while (uglyNums.size() < n) {
vector<int> nexts(k);
for (int i = 0; i < k; ++i)
nexts[i] = uglyNums[indices[i]] * primes[i];
const int next = ranges::min(nexts);
for (int i = 0; i < k; ++i)
if (next == nexts[i])
++indices[i];
uglyNums.push_back(next);
}
return uglyNums.back();
}
}; /* code provided by PROGIEZ */
313. Super Ugly Number LeetCode Solution in Java
class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
final int k = primes.length;
int[] indices = new int[k];
int[] uglyNums = new int[n];
uglyNums[0] = 1;
for (int i = 1; i < n; ++i) {
int[] nexts = new int[k];
for (int j = 0; j < k; ++j)
nexts[j] = uglyNums[indices[j]] * primes[j];
final int next = Arrays.stream(nexts).min().getAsInt();
for (int j = 0; j < k; ++j)
if (next == nexts[j])
++indices[j];
uglyNums[i] = next;
}
return uglyNums[n - 1];
}
} // code provided by PROGIEZ
313. Super Ugly Number LeetCode Solution in Python
class Solution:
def nthSuperUglyNumber(self, n: int, primes: list[int]) -> int:
k = len(primes)
nums = [1]
indices = [0] * k
while len(nums) < n:
nexts = [0] * k
for i in range(k):
nexts[i] = nums[indices[i]] * primes[i]
next = min(nexts)
for i in range(k):
if next == nexts[i]:
indices[i] += 1
nums.append(next)
return nums[-1] # code by PROGIEZ
