Last updated on July 20th, 2024 at 12:05 am

Here, We see Super Ugly Number LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Heap, Math

Companies

Google

Level of Question

Medium

Super Ugly Number LeetCode Solution

Problem Statement

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 n^th super ugly number.

The n^th 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].

1. Super Ugly Number Leetcode Solution C++

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        if (n == 1)
            return 1;
        int numPrimes = primes.size();
        vector<int> primeIndices(numPrimes, 0);
        int superUgly[n];
        superUgly[0] = 1;
        for (int i = 1; i < n; i++) {
            long minVal = INT_MAX;
            for (int j = 0; j < numPrimes; j++) {
                minVal = min(minVal, (long)primes[j] * superUgly[primeIndices[j]]);
            }
            superUgly[i] = (int)minVal;
            for (int j = 0; j < numPrimes; j++) {
                if (minVal == (long)primes[j] * superUgly[primeIndices[j]]) {
                    primeIndices[j]++;
                }
            }
        }
        return superUgly[n - 1];
    }
};

2. Super Ugly Number Leetcode Solution Java

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] ugly = new int[n+1];
        ugly[0]=1;
        int[] pointer = new int[primes.length];
        for(int i=1;i<n;i++) {
            int min=Integer.MAX_VALUE;
            int minIndex = 0;
            for(int j=0;j<primes.length;j++) {
                if(ugly[pointer[j]]*primes[j]<min) {
                    min=ugly[pointer[j]]*primes[j];
                    minIndex = j;
                }else if(ugly[pointer[j]]*primes[j]==min) {
                    pointer[j]++;
                }
            }
            ugly[i]=min;
            pointer[minIndex]++;
        }
        return ugly[n-1];
    }
}

3. Super Ugly Number Solution JavaScript

var nthSuperUglyNumber = function(n, primes) {
    let indeces = [];
    let currents = [];
    let i, l;
    for (i = 0, l = primes.length; i < l; i++) {
        indeces[i] = 0;
    }
    let out = [1];
    while (!out[n-1]) {
        for (i = 0, l = primes.length; i < l; i++) {
            currents[i] = out[indeces[i]] * primes[i];
        }
        let next = Math.min(...currents);
        out.push(next);
        for (i = 0, l = primes.length; i < l; i++) {
            if (next === out[indeces[i]] * primes[i]) {
                indeces[i] = indeces[i] + 1;
            }
        }
    }
    return out[n-1];
};

4. Super Ugly Number Solution Python

class Solution(object):
    def nthSuperUglyNumber(self, n, primes):
        uglies = [1]
        def gen(prime):
            for ugly in uglies:
                yield ugly * prime
        merged = heapq.merge(*map(gen, primes))
        while len(uglies) < n:
            ugly = next(merged)
            if ugly != uglies[-1]:
                uglies.append(ugly)
        return uglies[-1]