Write a program to find the nth
super ugly number.
Super ugly numbers are positive numbers whose all prime factors are in the
given prime list primes
of size k
.
Example:
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] of size 4.
Note:
1
is a super ugly number for any given primes
.primes
are in ascending order.k
≤ 100, 0 < n
≤ 106, 0 < primes[i]
< 1000.# @lc code=start
using LeetCode
function nth_super_ugly_number(n::Int, primes::Vector{Int})
dp = fill(1, n)
len = length(primes)
cur_min = primes[:]
ptrs = fill(1, len)
@inbounds for i in 2:n
minn = minimum(cur_min)
dp[i] = minn
@simd for pidx in 1:len
if minn == cur_min[pidx]
ptrs[pidx] += 1
cur_min[pidx] = dp[ptrs[pidx]] * primes[pidx]
end
end
end
return dp[end]
end
# @lc code=end
nth_super_ugly_number (generic function with 1 method)
This notebook was generated using Literate.jl.