Leetcode•Apr 07, 2026

Super Ugly Number

Hazrat Ali

Leetcode

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

Solution
var nthSuperUglyNumber = function(n, primes) {
    const k = primes.length;
    const dp = new Array(n).fill(0);
    dp[0] = 1;

    const pointers = new Array(k).fill(0);

    const values = primes.slice();

    for (let i = 1; i < n; i++) {

        let next = Math.min(...values);
        dp[i] = next;

        for (let j = 0; j < k; j++) {
            if (values[j] === next) {
                pointers[j]++;
                values[j] = dp[pointers[j]] * primes[j];
            }
        }
    }

    return dp[n - 1];
};



Comments