# Super Ugly Number **Difficulty:** MEDIUM [External](https://leetcode.com/problems/super-ugly-number) Canonical: https://scaleengineer.com/dsa/problems/super-ugly-number **Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming) **Data structures:** Array --- ## Problem 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 ## 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. **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. **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. ### Explanation 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; } } ``` ### 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. ## Dynamic Programming This approach uses dynamic programming. We can think of the sequence of super ugly numbers as the sorted result of merging `k` lists, where the `j`-th list is formed by multiplying all super ugly numbers by `primes[j]`. We build the sequence of super ugly numbers one by one. The next super ugly number is the minimum of the heads of these `k` lists. We use an array of pointers to keep track of the current head of each list. **Time:** O(n * k). The main loop runs `n` times, and inside it, we iterate `k` times to find the minimum candidate and another `k` times to update pointers. · **Space:** O(n + k), for the `ugly` array of size `n` and the `pointers` array of size `k`. **Pros:** Significantly more efficient than the brute-force approach.; Guaranteed to find the solution within typical time limits for the given constraints. **Cons:** The time complexity has a linear dependency on `k` (the number of primes), which might be slow if `k` is very large. ### Explanation This approach uses dynamic programming, treating the problem as merging `k` sorted lists, where `k` is the number of primes. Each list `L_j` consists of super ugly numbers multiplied by `primes[j]`. We build an array `ugly` of size `n` to store the super ugly numbers in sequence. The first super ugly number is 1. To find the `i`-th super ugly number, we find the minimum among the next possible candidates from each of the `k` lists. We use a `pointers` array to keep track of which ugly number to use next for each prime. After finding the minimum, we update the pointers for all lists that generated this minimum value to avoid duplicates and advance to the next candidate. ### Algorithm * Initialize an array `ugly` of size `n` and set `ugly[0] = 1`. * Initialize a `pointers` array of size `k` (length of `primes`) to all zeros. * Loop from `i = 1` to `n-1`: * Find the minimum value among `ugly[pointers[j]] * primes[j]` for all `j`. * Set `ugly[i]` to this minimum value. * Increment `pointers[j]` for all `j` where `ugly[pointers[j]] * primes[j]` equals the minimum value. * Return `ugly[n-1]`. ### Code Snippet ```java class Solution { public int nthSuperUglyNumber(int n, int[] primes) { if (n == 1) { return 1; } int[] ugly = new int[n]; ugly[0] = 1; int k = primes.length; int[] pointers = new int[k]; for (int i = 1; i < n; i++) { long minVal = Long.MAX_VALUE; for (int j = 0; j < k; j++) { minVal = Math.min(minVal, (long) ugly[pointers[j]] * primes[j]); } ugly[i] = (int) minVal; for (int j = 0; j < k; j++) { if ((long) ugly[pointers[j]] * primes[j] == ugly[i]) { pointers[j]++; } } } return ugly[n - 1]; } } ``` ### Algorithm * Create an array `ugly` of size `n` to store the super ugly numbers, with `ugly[0] = 1`. * Create an array `pointers` of size `k` (the number of primes), initialized to all zeros. `pointers[j]` will track the index of the ugly number to be multiplied by `primes[j]`. * Iterate from `i = 1` to `n-1` to fill the `ugly` array. * In each iteration, find the minimum value among all candidates `ugly[pointers[j]] * primes[j]`. This minimum is the next super ugly number, `ugly[i]`. * After finding the minimum, increment the pointer `pointers[j]` for any prime `primes[j]` that generated this minimum value. This handles duplicates and moves to the next candidate in that prime's sequence. ## Dynamic Programming with Min-Heap This approach is an optimization of the dynamic programming solution. Instead of linearly scanning `k` candidates to find the minimum in each step, we use a min-heap. The heap stores the next possible candidate from each of the `k` prime streams. This allows us to find the minimum candidate in `O(log k)` time instead of `O(k)`, leading to a more efficient overall solution. **Time:** O(n * log k). We find `n` ugly numbers. For each, we perform heap operations (extract-min and insert) which take `O(log k)` time, where `k` is the number of primes. · **Space:** O(n + k). O(n) for the `ugly` array and O(k) for the min-heap, which stores at most `k` elements. **Pros:** This is the most efficient approach for this problem.; The logarithmic time complexity for finding the minimum makes it scale well even with a large number of primes. **Cons:** Slightly more complex to implement compared to the standard DP approach due to heap management. ### Explanation This optimized DP approach uses a min-heap to efficiently find the next smallest super ugly number. We maintain an array `ugly` to store the results. The heap stores tuples representing the next potential super ugly number from each prime factor's stream. ### Algorithm * Initialize an `ugly` array of size `n` and set `ugly[0] = 1`. * Create a min-heap to store `long[]` arrays of `{value, prime, ugly_factor_index}`. * For each `prime` in `primes`, add `{prime, prime, 0}` to the heap. This corresponds to `prime * ugly[0]`. * Iterate from `i = 1` to `n-1`: * Extract the minimum entry `{val, p, idx}` from the heap. * To handle duplicates (e.g., 6 = 2*3 = 3*2), we only add `val` to our `ugly` array if it's larger than the previously added ugly number. * If `val > ugly[i-1]`, set `ugly[i] = val`. Otherwise, we process the duplicate and repeat the step for the same `i`. * Add the next candidate for the prime `p` to the heap. This is `p * ugly[idx + 1]`, so we push `{p * ugly[idx + 1], p, idx + 1}`. * Continue until the `ugly` array is filled. ### Code Snippet ```java import java.util.PriorityQueue; class Solution { public int nthSuperUglyNumber(int n, int[] primes) { if (n == 1) return 1; int[] ugly = new int[n]; ugly[0] = 1; PriorityQueue pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0])); for (int prime : primes) { pq.offer(new long[]{prime, prime, 0}); } int i = 1; while (i < n) { long[] entry = pq.poll(); long val = entry[0]; long p = entry[1]; int idx = (int) entry[2]; if (val > ugly[i - 1]) { ugly[i] = (int) val; i++; } long nextIdx = idx + 1; long nextVal = p * ugly[(int)nextIdx]; pq.offer(new long[]{nextVal, p, nextIdx}); } return ugly[n - 1]; } } ``` ### Algorithm * Initialize an `ugly` array of size `n` with `ugly[0] = 1`. * Use a min-heap (PriorityQueue) to keep track of the next candidates. * Initially, for each prime `p` in `primes`, push a tuple `(p, p, 0)` to the heap, representing `(value, prime, index)`. `value` is the candidate number, `prime` is the prime factor used, and `index` is the index from the `ugly` array. * Loop until `n` ugly numbers are found. In each step: * Pop the smallest candidate `(val, p, idx)` from the heap. * If this `val` is greater than the last found ugly number, it's a new unique ugly number. Add it to the `ugly` array. * Generate the next candidate for the prime `p` that was just used. The next candidate is `p * ugly[idx + 1]`. Push this new tuple `(p * ugly[idx + 1], p, idx + 1)` to the heap. # Solutions ### Java ```java class Solution { public int nthSuperUglyNumber(int n, int[] primes) { PriorityQueue 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; } } ``` ### CPP ```cpp class Solution { public: int nthSuperUglyNumber(int n, vector &primes) { priority_queue, greater> q; q.push(1); int x = 0; while (n--) { x = q.top(); q.pop(); for (int &k : primes) { if (x <= INT_MAX / k) { q.push(k * x); } if (x % k == 0) { break; } } } return x; } }; ``` ### Python ```python ''' The time complexity of the provided code is `O(n * k * log(n))` * where n is the input parameter n. * where k is the number of prime numbers in the input list For a single outer for loop iteration * Popping the smallest element from the heap using heappop(), which takes `O(log(n))` time complexity. * Pushing the new number into the heap using heappush(), which takes `O(log(n))` time complexity. * Therefore, the overall time complexity of the loop is `O(k * log(n))`, where k is the number of prime numbers in the input list. Since the loop runs for n iterations and each iteration has a time complexity of O(k * log(n)), the total time complexity of the code is `O(n * k * log(n))`. The space complexity of the code is `O(n)` due to the heap and the hash table * where n is the input parameter n. ''' from heapq import heappush , heappop class Solution : def nthSuperUglyNumber ( self , n : int , primes : List [ int ]) -> int : h = [ 1 ] # heap vis = { 1 } # hashtable to de-dup ans = 1 # initiator for _ in range ( n ): ans = heappop ( h ) for v in primes : nxt = ans * v if nxt not in vis : vis . add ( nxt ) heappush ( h , nxt ) return ans ############ ''' >>> a = {x:x+1 for x in range(10)} >>> a {0: 1, 1: 2, 2: 3, 3: 4, 4: 5, 5: 6, 6: 7, 7: 8, 8: 9, 9: 10} >>> a.items() [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9), (9, 10)] >>> a.values() [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] >>> a.keys() [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> float("-inf") == -math.inf True ''' class Solution : def nthSuperUglyNumber ( self , n : int , primes : List [ int ]) -> int : if n <= 0 or primes is None : return 0 nums = [ 1 ] index = [ 0 ] * len ( primes ) while len ( nums ) < n : minv = float ( 'inf' ) for i in range ( len ( primes )): minv = min ( minv , primes [ i ] * nums [ index [ i ]]) nums . append ( minv ) for i in range ( len ( primes )): if primes [ i ] * nums [ index [ i ]] == minv : index [ i ] += 1 return nums [ - 1 ] if __name__ == '__main__' : # if no de-dup, result will be: # [1, 2, 4, 7, 8, 13, 14, 14, 16, 19, 26, 26] # corret: [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] print ( Solution (). nthSuperUglyNumber ( 12 , [ 2 , 7 , 13 , 19 ])) ############# class Solution : # not that good, just for reference def nthSuperUglyNumber ( self , n : int , primes : List [ int ]) -> int : q = [ 1 ] x = 0 mx_int = ( 1 << 31 ) - 1 for _ in range ( n ): x = heappop ( q ) for k in primes : if x <= mx_int // k : # make sure not overflow int type heappush ( q , k * x ) if x % k == 0 : # to avoid duplicates, eg [2,3,5], when x is 6 break # print(x) # print(list(q)) return x ''' primes = [2,3,5] n = 10 result should be: 12 [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] for the print enabled, I got: 1 [2, 3, 5] 2 [3, 5, 4] ==> heappop got 3, 3%3==0 so still added 3*3=9, but not added 3*5=15 3 [4, 5, 6, 9] 4 [5, 8, 6, 9] 5 [6, 8, 9, 10, 15, 25] 6 [8, 10, 9, 25, 15, 12] 8 [9, 10, 12, 25, 15, 16] 9 [10, 15, 12, 25, 16, 18, 27] 10 [12, 15, 18, 25, 16, 27, 20] 12 [15, 16, 18, 25, 20, 27, 24] ''' ```