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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Super Ugly Number and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →