We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Super Ugly Number

Number: 313

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

A super ugly number is a positive integer whose prime factors are in the given array primes. Given an integer n and an array of primes, return the nth super ugly number. Note that 1 is considered a super ugly number since it has no prime factors.

Key Insights

  • We need to generate super ugly numbers in increasing order.
  • This problem is an extension of the Ugly Number II problem but with a customizable list of primes.
  • Dynamic Programming (DP) can be used by maintaining an array of already computed super ugly numbers.
  • Use multiple pointers (one for each prime) to generate new candidates.
  • In each step, multiply the current DP values by each prime using the pointers, then choose the smallest candidate to ensure the sequence is ordered.
  • Increment pointers for all primes that reach the candidate to avoid duplicate numbers.

Space and Time Complexity

Time Complexity: O(n * k), where n is the number of super ugly numbers to generate and k is the number of primes. Space Complexity: O(n + k) for the DP array and the pointer array.

Solution

We implement a dynamic programming solution using multiple pointers. We maintain a DP array where dp[i] holds the ith super ugly number. For each prime in primes, an index pointer tracks which element in dp should be multiplied next by that prime. In each iteration, we calculate the next candidate candidate numbers from the current pointers and choose the smallest one as the next super ugly number. Any pointer that contributes to this number is incremented so that duplicate multiplications are avoided. This efficiently generates the sequence up to the nth super ugly number.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java.

# Python solution for Super Ugly Number
def nthSuperUglyNumber(n, primes):
    # Total number of primes
    k = len(primes)
    # dp array to store super ugly numbers, starting with 1 as the first super ugly number
    dp = [1] * n
    # indices array, one pointer for each prime
    indices = [0] * k
    # next_vals holds the next candidate for each prime
    next_vals = list(primes)
    
    # Build the dp list from 1 to n
    for i in range(1, n):
        # Determine the next super ugly number
        next_ugly = min(next_vals)
        dp[i] = next_ugly
        
        # Increment pointer(s) for each prime that produced the next_ugly number
        for j in range(k):
            if next_vals[j] == next_ugly:
                indices[j] += 1
                next_vals[j] = dp[indices[j]] * primes[j]
                
    return dp[-1]

# Example usage:
print(nthSuperUglyNumber(12, [2, 7, 13, 19]))  # Expected output: 32
← Back to All Questions