Scale Engineer

Super Ugly Number

Med
#0300Time: 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: O(1), as it only uses a few variables to keep track of the count and the current number.
Patterns
MathDynamic Programming
Data structures
Array

Prompt

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

 

Constraints:

  • 1 <= n <= 105
  • 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

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

O(1), as it only uses a few variables to keep track of the count and the current number.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem