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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Super Ugly Number

Difficulty: Medium

Problem Description

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.

Key Insights

  • Super ugly numbers are generated by multiplying the prime factors provided in the primes array.
  • The sequence starts with 1, which is considered a super ugly number by convention.
  • The problem can be efficiently solved using a min-heap (or priority queue) to generate numbers in increasing order.
  • Each time a super ugly number is found, it can be multiplied by each prime factor to generate new candidates.

Space and Time Complexity

Time Complexity: O(n * k), where n is the index of the super ugly number we want to find and k is the number of prime factors. Space Complexity: O(k), to store the current indices and the next values for each prime factor.

Solution

The approach involves using a min-heap to store the next potential super ugly numbers. We initialize the heap with the first super ugly number (1) and iterate to find the next super ugly numbers by repeatedly extracting the smallest number from the heap, pushing its multiples (generated by multiplying with each prime) back into the heap.

Code Solutions

import heapq

def nthSuperUglyNumber(n, primes):
    heap = []
    ugly_numbers = [1]  # The first super ugly number is always 1
    heapq.heappush(heap, 1)
    seen = {1}

    for _ in range(1, n):
        current_ugly = heapq.heappop(heap)
        for prime in primes:
            new_ugly = current_ugly * prime
            if new_ugly not in seen:
                seen.add(new_ugly)
                heapq.heappush(heap, new_ugly)

    return heapq.heappop(heap)
← Back to All Questions