algoadvance

Leetcode 313. Super Ugly Number

Problem Statement

A super ugly number is a positive integer whose prime factors are in the given list of primes primes. Given an integer n and a list of integers primes, return the n-th super ugly number.

Example:

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

Clarifying Questions

  1. What is the range of n?
    • Typically 1 <= n <= 10^6.
  2. Will primes always contain prime numbers between 1 to 100?
    • Yes, it’s guaranteed in the problem statement.
  3. Can primes contain duplicates?
    • No, all elements in primes are distinct.

Solution Strategy

To solve this problem, we can use a variation of Dijkstra’s algorithm, often employed for finding the n-th ugly number in such problems. Here’s a step-by-step breakdown of the strategy:

  1. Data Structures:
    • Use a min-heap (priority queue) to keep track of the next potential super ugly numbers.
    • Maintain an array ugly to store the first n super ugly numbers.
  2. Initialization:
    • The first super ugly number is always 1.
    • Push initial elements into the heap, one for each prime in primes, initialized with the prime value itself.
  3. Heap Operations:
    • Extract the smallest element from the heap.
    • If this is a new super ugly number (i.e., not a duplicate), add it to the ugly array.
    • For each extracted element, derive the next potential super ugly number by multiplying it with each prime, and push the new products back into the heap.
  4. Avoid Duplicates:
    • Use a set to track elements that have already been added to the heap to avoid duplicates.
  5. Termination:
    • Continue the above steps until we have n elements in the ugly array.

Code Implementation

import java.util.*;

public class SuperUglyNumber {
    public int nthSuperUglyNumber(int n, int[] primes) {
        // Min-heap to keep track of the current minimal values.
        PriorityQueue<Long> minHeap = new PriorityQueue<>();
        // Set to avoid duplicate entries in the heap.
        Set<Long> seen = new HashSet<>();
        
        // Initialize the heap with primes.
        for (int prime : primes) {
            minHeap.add((long) prime);
            seen.add((long) prime);
        }
        
        // Initialize the first ugly number.
        long[] ugly = new long[n];
        ugly[0] = 1;

        for (int i = 1; i < n; i++) {
            // Extract the smallest number from the heap.
            long nextUgly = minHeap.poll();
            
            // Store the next ugly number in our array.
            ugly[i] = nextUgly;
            
            // For every prime, calculate the new number by multiplying with next ugly number.
            for (int prime : primes) {
                long newUgly = nextUgly * prime;
                // Add to heap only if it hasn't been seen before.
                if (seen.add(newUgly)) {
                    minHeap.add(newUgly);
                }
            }
        }
        
        return (int) ugly[n - 1];
    }

    public static void main(String[] args) {
        SuperUglyNumber solution = new SuperUglyNumber();
        int n = 12;
        int[] primes = {2, 7, 13, 19};
        System.out.println(solution.nthSuperUglyNumber(n, primes));  // Output: 32
    }
}

Time Complexity

In summary, this approach efficiently finds the n-th super ugly number using a min-heap and avoids unnecessary duplicates through the use of a set for tracking.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI