Super Ugly Number
MedPrompt
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 <= 1051 <= primes.length <= 1002 <= primes[i] <= 1000primes[i]is guaranteed to be a prime number.- All the values of
primesare 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 = 0and a numbernum = 0. * Loop indefinitely untilcountreachesn. * In each iteration, incrementnumand check if it's a super ugly number using a helper function. * If it is, incrementcount. * Whencountequalsn, the currentnumis the answer. * The helper functionisSuperUgly(k, primes)checks if a numberkis super ugly by repeatedly dividing it by the primes in theprimesarray. Ifkbecomes 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.
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.
Algorithm
- Create an array
uglyof sizento store the super ugly numbers, withugly[0] = 1. * Create an arraypointersof sizek(the number of primes), initialized to all zeros.pointers[j]will track the index of the ugly number to be multiplied byprimes[j]. * Iterate fromi = 1ton-1to fill theuglyarray. * In each iteration, find the minimum value among all candidatesugly[pointers[j]] * primes[j]. This minimum is the next super ugly number,ugly[i]. * After finding the minimum, increment the pointerpointers[j]for any primeprimes[j]that generated this minimum value. This handles duplicates and moves to the next candidate in that prime's sequence.
Walkthrough
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]; } }
Complexity
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`.
Trade-offs
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 ifkis very large.
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.
Algorithm
- Initialize an
uglyarray of sizenwithugly[0] = 1. * Use a min-heap (PriorityQueue) to keep track of the next candidates. * Initially, for each primepinprimes, push a tuple(p, p, 0)to the heap, representing(value, prime, index).valueis the candidate number,primeis the prime factor used, andindexis the index from theuglyarray. * Loop untilnugly numbers are found. In each step: * Pop the smallest candidate(val, p, idx)from the heap. * If thisvalis greater than the last found ugly number, it's a new unique ugly number. Add it to theuglyarray. * Generate the next candidate for the primepthat was just used. The next candidate isp * ugly[idx + 1]. Push this new tuple(p * ugly[idx + 1], p, idx + 1)to the heap.
Walkthrough
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 = 23 = 32), 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<long[]> 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]; } }
Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}class Solution {public: int nthSuperUglyNumber(int n, vector<int> &primes) { priority_queue<int, vector<int>, greater<int>> 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; }};''' 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] '''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.