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 n
th super ugly number.
For example:
n = 12
and primes = [2, 7, 13, 19]
, what is the 12th super ugly number? The sequence of the first 12 super ugly numbers is: [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]
. Therefore, the answer is 32
.n = 1
and primes = [2, 3, 5]
, what is the 1st super ugly number? The answer is 1
.Write a function to find the nth super ugly number given n
and primes
.
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.
For example:
A brute force solution would involve generating all possible numbers and checking if they are super ugly numbers. This is highly inefficient.
We can use dynamic programming to solve this problem efficiently. We maintain an array ugly
to store the super ugly numbers, and an array pointers
to track the index of each prime number in the ugly
array. For each index i
from 1 to n-1
, we find the minimum value among ugly[pointers[j]] * primes[j]
for all j
and update the ugly
array. If a prime number generates the minimum ugly number, its corresponding pointer is incremented. This approach ensures that we only consider the necessary multiplications, and reduces time complexity.
def nthSuperUglyNumber(n, primes):
ugly = [0] * n
ugly[0] = 1
pointers = [0] * len(primes)
for i in range(1, n):
min_ugly = float('inf')
for j in range(len(primes)):
min_ugly = min(min_ugly, ugly[pointers[j]] * primes[j])
ugly[i] = min_ugly
for j in range(len(primes)):
if ugly[pointers[j]] * primes[j] == min_ugly:
pointers[j] += 1
return ugly[n - 1]
n = 1
: should return 1.primes
is empty. (Problem statement guarantees primes.length >= 1.)n
that might cause integer overflow (problem statement guarantees a 32-bit signed integer)ugly
array and k is for the pointers
array.