/313. Nth Super Ugly Number

313. Nth Super Ugly Number

Medium
Arrays46% acceptance

Given an integer k and a list of distinct prime numbers prime_list, return the k-th positive integer whose prime factors are only from prime_list. The sequence starts with 1 as the first such number.

Example 1

Input: k=5, prime_list=[3,5,7]

Output: 9

Explanation: The sequence is [1,3,5,7,9], so the 5th number is 9.

Example 2

Input: k=7, prime_list=[2,11]

Output: 22

Explanation: The sequence is [1,2,4,8,11,16,22], so the 7th number is 22.

Constraints

  • 1 <= k <= 105
  • 1 <= len(prime_list) <= 100
  • 2 <= prime_list[i] <= 1000
  • prime_list[i] is a prime number
  • All values in prime_list are unique and sorted in ascending order
Python (current runtime)

Case 1

Input: k=6, prime_list=[2,3,5]

Expected: 8

Case 2

Input: k=10, prime_list=[2,5]

Expected: 32

Case 3

Input: k=4, prime_list=[13,17]

Expected: 221

Case 4

Input: k=8, prime_list=[2,7]

Expected: 28

Case 5

Input: k=3, prime_list=[5,11]

Expected: 11