{x}
blog image

Super Ugly Number

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.

 

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

 

Constraints:

  • 1 <= n <= 105
  • 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.

Solution Explanation for Super Ugly Number

The problem asks to find the nth super ugly number, where a super ugly number is a positive integer whose prime factors are all within a given primes array.

Approach 1: Priority Queue (Min-Heap)

This approach leverages a min-heap data structure to efficiently find the nth super ugly number. The core idea is as follows:

  1. Initialization: Start with a min-heap containing only the number 1 (the first super ugly number).

  2. Iteration: Repeatedly extract the minimum element from the heap. This is the next super ugly number in the sequence.

  3. Generation: For each extracted super ugly number x, generate its multiples by each prime number in primes. These multiples are potential candidates for future super ugly numbers. Add them to the heap.

  4. Duplicate Handling: The heap might contain duplicate values. Efficiently handling duplicates is crucial for performance. We can either explicitly check for duplicates before inserting or implicitly handle them by iteratively removing duplicates from the heap top before proceeding to the next iteration. The code examples shown below demonstrate different ways to handle this aspect.

  5. Termination: The loop continues until n super ugly numbers have been extracted. The last extracted number is the nth super ugly number.

Time Complexity: O(n * m * log(nm)), where n is the target nth number and m is the number of primes. The log(nm) factor comes from heap operations. In the worst case, we might add almost all generated multiples to the heap.

Space Complexity: O(n*m) in the worst case, due to the heap storing generated multiples.

Code Examples (with explanations)

Python3

import heapq
 
class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        heap = [1]  # Initialize min-heap with 1
        seen = set([1]) # Keep track of elements already in heap to avoid duplicates
 
        for i in range(n):
            curr = heapq.heappop(heap)  # Get the smallest super ugly number
 
            for p in primes:
                next_ugly = curr * p
                if next_ugly not in seen and next_ugly <= 2**31 -1: #check for duplicates and integer overflow
                    heapq.heappush(heap, next_ugly)
                    seen.add(next_ugly)
 
        return curr # the last extracted number is the nth super ugly number

Java

import java.util.PriorityQueue;
import java.util.HashSet;
import java.util.Set;
 
class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        PriorityQueue<Long> pq = new PriorityQueue<>(); // Use Long to avoid integer overflow
        pq.offer(1L);
        Set<Long> seen = new HashSet<>();
        seen.add(1L);
 
        for (int i = 0; i < n; i++) {
            long curr = pq.poll();
 
            for (int p : primes) {
                long next = curr * p;
                if (!seen.contains(next)) {
                    pq.offer(next);
                    seen.add(next);
                }
            }
        }
        return (int) pq.peek(); //Casting to int is safe since the problem guarantees it to be a 32-bit integer
    }
}

C++

#include <queue>
#include <set>
#include <vector>
 
using namespace std;
 
class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        priority_queue<long long, vector<long long>, greater<long long>> pq; //Use long long to handle potential overflow
        pq.push(1);
        set<long long> seen;
        seen.insert(1);
 
        for (int i = 0; i < n; ++i) {
            long long curr = pq.top();
            pq.pop();
 
            for (int p : primes) {
                long long next = curr * p;
                if (seen.find(next) == seen.end()) {
                    pq.push(next);
                    seen.insert(next);
                }
            }
        }
        return (int)pq.top(); //Safe cast as guaranteed by problem constraints
    }
};

Go (using a custom heap for efficiency)

import (
	"container/heap"
	"math"
)
 
type Ugly struct {
	value int
	index int
}
 
type hp struct {
	data []Ugly
}
 
func (h hp) Len() int { return len(h.data) }
func (h hp) Swap(i, j int) { h.data[i], h.data[j] = h.data[j], h.data[i] }
func (h hp) Less(i, j int) bool {
	return h.data[i].value < h.data[j].value
}
func (h *hp) Push(x interface{}) {
	*h = hp{append(h.data, x.(Ugly))}
}
func (h *hp) Pop() interface{} {
	old := h.data
	n := len(old)
	x := old[n-1]
	h.data = old[0 : n-1]
	return x
}
 
func nthSuperUglyNumber(n int, primes []int) int {
    h := hp{[]Ugly{{value:1, index:0}}}
    heap.Init(&h)
    visited := map[int]bool{1: true}
 
    for i := 0; i < n; i++ {
        curr := heap.Pop(&h).(Ugly)
        if curr.value > math.MaxInt32 {
          return math.MaxInt32;
        }
        for _, p := range primes {
            next := curr.value * p
            if _, ok := visited[next]; !ok && next <= math.MaxInt32 {
                heap.Push(&h, Ugly{value: next, index:0})
                visited[next] = true
            }
        }
    }
 
    return heap.Pop(&h).(Ugly).value
}

These examples demonstrate efficient implementations of the min-heap approach, handling duplicates and potential integer overflow. Remember to choose the implementation that best suits your preferred language and coding style. The time and space complexity analysis remains the same for all implementations.