Super Ugly Number
Medium · Heap & Counting · Array · Math · Dynamic Programming · Heap (Priority Queue)
Problem
A super ugly number is a positive integer whose prime factors all appear in a given list primes. The number 1 counts as super ugly.
Given n and primes, return the n-th super ugly number in increasing order. The answer fits in a signed 32-bit integer.
Examples
Input: n = 6, primes = [3,5] Output: 25
The sequence is 1, 3, 5, 9, 15, 25.
Input: n = 1, primes = [7] Output: 1
The first super ugly number is always 1.
Input: n = 12, primes = [2,7,13,19] Output: 32
The sequence is 1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32.
Constraints
- 1 <= n <= 10^5
- 1 <= primes.length <= 100
- 2 <= primes[i] <= 1000
- every primes[i] is prime
- primes is sorted in strictly increasing order
Approaches
- One pointer per prime, scanned each step — time O(n · k), space O(n + k)
Follow-up
The pointer idea is a k-way merge of the lists ugly · p. The use cases count the super ugly numbers up to a limit and test a single number.
Related problems
Start free on Cariara · Coding problems · System design studio
