Skip to main content

313. Super Ugly Number

medium

Generalize Ugly Number II to an arbitrary set of allowed primes: find the nth super-ugly number. The k-pointer DP scales the trick from 3 primes to any k.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

  • 1 <= n <= 10^5
  • 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.

Examples

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].

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

This is Ugly Number II with k primes instead of 3. The three-pointer DP generalizes to a k-pointer DP.

Hint 2

Allocate ugly[0..n-1] with ugly[0] = 1 and an array of pointers indices[0..k-1] starting at 0.

Hint 3

For each next slot, the candidate for prime p is ugly[indices[p]] * primes[p]. Take the minimum across all primes.

Hint 4

Increment EVERY pointer whose candidate equals the new minimum, to dedup. The candidate-recompute can be cached for performance.

Solution approach

Reveal approach

k-pointer DP, the natural generalization of Ugly Number II. Allocate ugly[0..n-1] with ugly[0] = 1, plus k indices initialized to 0. For each new slot k from 1 to n-1: scan the k primes to compute candidate_p = ugly[indices[p]] * primes[p]; take the minimum. Write ugly[k] = min. Then for every prime whose candidate equals the new ugly[k], advance its pointer (this handles dedupes like when two prime products tie). Return ugly[n-1]. O(n * k) time, O(n + k) space. Min-heap alternative: O(n * k * log(n * k)) time — slower constants but cleaner code. For the given bounds (n = 10^5, k = 100) the DP is preferred.

Complexity

Time
O(n * k)
Space
O(n + k)

Related patterns

  • dynamic-programming
  • math
  • heap
  • merge

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

More Math practice problems

See all Math problems →