Super Ugly Number

MEDIUM

Description

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

Constraints:

1 <= n <= 10⁵
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.

Approaches

Checkout 3 different approaches to solve Super Ugly Number. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Trial Division

This naive approach iterates through all positive integers starting from 1. For each integer, it checks if it qualifies as a super ugly number. A number is super ugly if all of its prime factors are present in the given primes array. We keep counting the super ugly numbers we find until we reach the n-th one.

Algorithm

Initialize a counter count = 0 and a number num = 0. * Loop indefinitely until count reaches n. * In each iteration, increment num and check if it's a super ugly number using a helper function. * If it is, increment count. * When count equals n, the current num is the answer. * The helper function isSuperUgly(k, primes) checks if a number k is super ugly by repeatedly dividing it by the primes in the primes array. If k becomes 1, it's a super ugly number.

The brute-force approach involves iterating through positive integers starting from 1 and checking if each number is a super ugly number. We maintain a count of the super ugly numbers found. When the count reaches n, we return the current number. A helper function, isSuperUgly, is used to determine if a number's prime factors are all within the given primes array. This is done by trial division: repeatedly dividing the number by each prime in the primes list. If the number reduces to 1, it's a super ugly number. ### Algorithm * Initialize count = 0 and num = 0. * Loop until count equals n: * Increment num. * If isSuperUgly(num, primes) is true, increment count. * Return num. ### isSuperUgly(num, primes) * For each prime p in primes, repeatedly divide num by p as long as it's divisible. * If the final num is 1, return true; otherwise, return false. ### Code Snippet java class Solution { public int nthSuperUglyNumber(int n, int[] primes) { if (n == 1) { return 1; } int count = 1; // Start with 1 being the first super ugly number int num = 1; while (count < n) { num++; if (isSuperUgly(num, primes)) { count++; } } return num; } private boolean isSuperUgly(int num, int[] primes) { long tempNum = num; for (int p : primes) { while (tempNum % p == 0) { tempNum /= p; } } return tempNum == 1; } }

Complexity Analysis

Time Complexity: O(M * k * log M), where `M` is the value of the n-th super ugly number and `k` is the number of primes. For each number up to `M`, we perform trial division which takes `O(k * log num)` time. This is prohibitively slow.Space Complexity: O(1), as it only uses a few variables to keep track of the count and the current number.

Pros and Cons

Pros:

Simple to understand and implement.
Uses constant extra space.

Cons:

Extremely inefficient and will not pass the time limits for the given constraints.
The value of the nth super ugly number can be very large, leading to a huge number of iterations.

Code Solutions

Checking out 3 solutions in different languages for Super Ugly Number. Click on different languages to view the code.

class Solution {
public
  int nthSuperUglyNumber(int n, int[] primes) {
    PriorityQueue<Integer> q = new PriorityQueue<>();
    q.offer(1);
    int x = 0;
    while (n-- > 0) {
      x = q.poll();
      while (!q.isEmpty() && q.peek() == x) {
        q.poll();
      }
      for (int k : primes) {
        if (k <= Integer.MAX_VALUE / x) {
          q.offer(k * x);
        }
        if (x % k == 0) {
          break;
        }
      }
    }
    return x;
  }
}

Video Solution

Watch the video walkthrough for Super Ugly Number

Patterns:

MathDynamic Programming

Data Structures:

Array