Super Ugly Number

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.

Examples

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^5
• 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.

Solution

Method 1 - Using MinHeap and Not Checking Duplicates

We can use logic similar [Merge K Sorted Lists](merge-k-sorted-lists):

ugly number                       k sorted list
    1                            2     7    13   19     1 * [2,7,13,19]
    |                            |     |    |    |
    2                            4     14   26   38     2 * [2,7,13,19]
    |                            |     |    |    |
    4                            8     28   52   76     4 * [2,7,13,19]
    |                            |     |    |    |              
    7                            14    49   91   133    7 * [2,7,13,19]
    |                            |     |    |    |
    8                            16    56   ...   ...   8 * [2,7,13,19]
    |                            |     |    |     |
    .                            .     .     .    .
    .                            .     .     .    .
    .                            .     .     .    .

We can see that each prime number in primes[] form a sorted list, and now our job is to merge them and find the nth minimum.

Here we don't have the next pointer for each node to trace the next potential candidate. But as we can see in the graph, we can make use of the ugly number we have produced so far!

We can create a triplet for the minHeap, where, each entry has three parts: {num, prime, index}:

• num represents the value of the node, 
• prime means which sorted list this node is in, and 
• index tells us how far we have gone in that list, it works like the next pointer in linkedlist, help us find the next node in that sorted list.

Code

Java

public int nthSuperUglyNumber(int n, int[] primes) {
	PriorityQueue<int[] > queue = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
	for (int i = 0; i<primes.length; i++) {
		queue.offer(new int[] { primes[i], primes[i], 0 });
	}

	int[] ans = new int[n + 1];
	ans[0] = 1;

	int i = 1;
	while (i < n) {
		int[] node = queue.poll();
		int num = node[0], prime = node[1], idx = node[2];

		// ignore duplicate
		if (num != ans[i - 1]) {
			ans[i] = num;
			i++;
		}
		queue.offer(new int[] { prime * ans[idx + 1], prime, idx + 1 });
	}
	return ans[n - 1];
}

Complexity

• ⏰ Time complexity: O(kn log k), Could have been nlogk but we have so many duplicates.
• 🧺 Space complexity: O(n + k)

Method 2 - Using MinHeap and Handling Duplicates

Note it is not working: ❌. Need to fix it.

Code

Java

public int nthSuperUglyNumber(int n, int[] primes) {
	PriorityQueue<int[] > queue = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
	Set<Integer> set = new HashSet<>();
	for (int i = 0; i<primes.length; i++) {
		queue.offer(new int[] { primes[i], primes[i], 0 });
		set.add(primes[i]);
	}

	int[] ans = new int[n + 1];
	ans[0] = 1;

	int i = 1;
	while (i < n) {
		int[] node = queue.poll();
		int num = node[0], prime = node[1], idx = node[2];

		ans[i++] = num;
		int newIdx = idx+1;
		int newNum = prime * ans[newIdx + 1];
		while(set.contains(newNum)) {
			newNum = prime * ans[newIdx++];
		}
		queue.offer(new int[] { newNum, prime, newIdx });
		set.add(newNum);
	}
	return ans[n - 1];
}

Method 3 - Using MinHeap and Generate All Numbers

Code

Java

public int nthSuperUglyNumber(int n, int[] primes) {
	Queue<Integer> pq = new PriorityQueue<>();
	pq.offer(1);
	for (int p : primes) {
		pq.offer(p);
	}
	// note loop is till n-1 
	// as later we are removing n-1th element as return statement
	for (int i=0; i< n-1; i++) {
		int cur = pq.poll();
		for (int p : primes) {  //each one pop out should multiply the array
			long mult = (long)cur * (long)x;
			if (mult < Integer.MAX_VALUE) {
				pq.offer((int)mult);
			}
		}
		while (pq.peek() == cur) {  // It is sorted, so if duplicate, only happen at root, poll it
			pq.poll();
		}
	}
	return pq.poll();
}

Complexity

• ⏰ Time complexity: O(n*m), where for nth number, we are using array of m primes.
• 🧺 Space complexity: O(m)

Method 4 - Using Arrays Instead of Heap

Keep adding minimum values to results and updating the time value for the chosen prime number in each loop.

Code

Java

public int nthSuperUglyNumber(int n, int[] primes) {
	int[] times = new int[primes.length];
	int[] ans = new int[n];
	ans[0] = 1; // first is 1

	for (int i = 1; i<n; i++) {
		int min = Integer.MAX_VALUE;
		for (int j = 0; j<primes.length; j++) {
			min = Math.min(min, primes[j] * result[times[j]]);
		}

		result[i] = min;

		for (int j = 0; j<times.length; j++) {
			if (ans[times[j]] * primes[j] == min) {
				times[j]++;
			}
		}
	}

	return ans[n - 1];
}