Super Ugly Number LeetCode Solution

Last updated on October 5th, 2024 at 09:25 pm

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

Super Ugly Number LeetCode Solution

Problem Statement

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

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]
Scroll to Top