Super Ugly Number LeetCode Solution | Easy Approach

Minimum Cost to Merge Stones
Share:

Super Ugly Number 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 <= 106
  • 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.

Super Ugly Number Solutions

Time: O(nk)
Space: O(k)

C++

class Solution {
 public:
  int nthSuperUglyNumber(int n, vector<int>& primes) {
    const int k = primes.size();
    vector<int> indices(k);
    vector<int> uglyNums{1};

    while (uglyNums.size() < n) {
      vector<int> nexts(k);
      for (int i = 0; i < k; ++i)
        nexts[i] = uglyNums[indices[i]] * primes[i];
      const int next = *min_element(begin(nexts), end(nexts));
      for (int i = 0; i < k; ++i)
        if (next == nexts[i])
          ++indices[i];
      uglyNums.push_back(next);
    }

    return uglyNums.back();
  }
};

Java

 
 class Solution {
  public int nthSuperUglyNumber(int n, int[] primes) {
    final int k = primes.length;
    int[] indices = new int[k];
    int[] uglyNums = new int[n];
    uglyNums[0] = 1;

    for (int i = 1; i < n; ++i) {
      int[] nexts = new int[k];
      for (int j = 0; j < k; ++j)
        nexts[j] = uglyNums[indices[j]] * primes[j];
      final int next = Arrays.stream(nexts).min().getAsInt();
      for (int j = 0; j < k; ++j)
        if (next == nexts[j])
          ++indices[j];
      uglyNums[i] = next;
    }

    return uglyNums[n - 1];
  }
}

Python


class Solution:
  def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
    k = len(primes)
    nums = [1]
    indices = [0] * k

    while len(nums) < n:
      nexts = [0] * k
      for i in range(k):
        nexts[i] = nums[indices[i]] * primes[i]
      next = min(nexts)
      for i in range(k):
        if next == nexts[i]:
          indices[i] += 1
      nums.append(next)

    return nums[-1]

Watch Tutorial

Checkout more Solutions here

Leave a Comment

Your email address will not be published. Required fields are marked *

x