__Introduction__

__Introduction__

Problems on prime numbers are a hot selling topic for coding competitions and interviews as they tend to check the candidate’s logical reasoning. Every year, variations of existing problems are added, trying to confuse the candidate, and to some extent, their motive is achieved as many are not able to solve them. But the solution to such complex problems lies in the very basics itself, and if one has a proper grip on the basics, they can solve any question no matter what the level of that question is.

So let’s try to solve one such question, which is a variation of Ugly Numbers.

Also Read, __Byte Array to String__

__Problem Statement__

__Problem Statement__You are given an array, * PRIMES[]*, consisting of

*prime numbers. A super ugly number is one whose prime factors lie in this array*

**‘N’***. Your task is to find the*

**PRIMES[]***super ugly number.*

**Kth**Also,* 1* is considered to be the first super ugly number.

Let us try to understand this with the help of an example:

__Example__

__Example__

**N = 2**

**PRIMES[]= {2, 3}**

**K = 6**

The super ugly numbers will be**→ {1, 2, 3, 4, 6, 8,9} **

The * 6th *super ugly number is

**8.** 2. **N = 3**

**PRIMES[2, 3, 7]**

**K = 8**

The super ugly numbers will be**→ {1, 2, 3, 4, 6, 7, 8, 9} **

The * 8th *super ugly number is

**9.**Having understood the problem completely, try solving the * problem* yourself.

Now, let us solve this problem.

__Priority Queue__

__Priority Queue__

__Algorithm__

__Algorithm__-
We use a min-heap
,__priority queue__to store the elements in ascending order.**PRIORITY_QUEUE,** - First, we insert the elements of the
array into the priority queue.**PRIMES[]** - Now one by one, we will pop the elements of the priority queue. It will always be the smallest element of the priority queue, and we will maintain a count of the number of elements being popped.
- Subsequently, we will store this element in a temporary variable, and multiply this with each element of the original
array and push it into the priority queue.**PRIMES[]** - When the count becomes equal to
we will store the result and return it. In this way, we will get the**K,**super ugly number quite easily.**K**^{th}

__Example__

__Example__

**N = 2**

**PRIMES[]= {2, 3}**

**K = 6**

Let * PRIORITY_QUEUE* be our initially empty priority queue.

Let * COUNT* be the super ugly number that is being popped out of the queue.

Let * NUM* be the first element that is being popped out of the queue.

- First, we will push the elements of
into the PRIORITY_QUEUE.**PRIMES**

**PRIORITY_QUEUE = {2, 3}**

**COUNT = 1**

- Popping the first element of PRIORITY_QUEUE,
**NUM = 2**

**COUNT = 2**

Elements to be inserted **= 2 * 2, 2 * 3**

** = 4, 6**

**PRIORITY_QUEUE****= {3, 4, 6}**

- Popping the first element of PRIORITY_QUEUE,
**NUM = 3**

**COUNT = 3**

Elements to be inserted** = 3 * 2, 3 * 3**

** = 6, 9**

**PRIORITY_QUEUE****= {4, 6, 6,9}**

- Popping the first element of PRIORITY_QUEUE,
**NUM = 4**

**COUNT = 4**

Elements to be inserted** = 4 * 2, 4 * 3**

** = 8, 12**

**PRIORITY_QUEUE****= {6, 6, 8, 9,12}**

- Popping the first element of PRIORITY_QUEUE,
**NUM = 6**

**COUNT = 5**

Elements to be inserted** = 6 * 2, 6 * 3**

** = 12, 18**

**PRIORITY_QUEUE= {6, 8, 9,12, 12, 18}**

- Popping the first element of PRIORITY_QUEUE,
**NUM = 6**

* COUNT = 5* (Remains same-duplicacy)

Elements to be inserted** = 6 * 2, 6 * 3**

** = 12, 18**

**PRIORITY_QUEUE****= {8, 9,12, 12, 18}**

- Popping the first element of PRIORITY_QUEUE,
**NUM = 8**

**COUNT = 6**

Loop breaks since **COUNT = K**

Thus, the * 6th *super ugly number is

**8.****Implementation**

**Implementation**

__Program__

__Program__```
// C++ program to find super ugly numbers using a priority queue.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// Function to return the Kth super ugly number.
int superUgly(vector<int> & primes, int n, int k)
{
// 'K' cannot be negative or zero.
if (k <= 0)
return -1;
// 1 is the first Super Ugly Number.
if (k == 1){
return 1;
}
// Declaring a min-heap priority queue.
priority_queue<int, vector<int>, greater<int>>priorityQueue;
// Pushing all the elements of 'PRIME' array in the priority queue.
for (int i = 0; i < n; i++)
{
priorityQueue.push(primes[i]);
}
// Initialising count with 1 because 1 is the first super ugly number.
int count = 1, num;
while (count < k)
{
// Storing the minimum value from the priority queue and removing it.
num = priorityQueue.top();
priorityQueue.pop();
// To avoid counting duplicate numbers, we will not increment the count.
if (num != priorityQueue.top())
{
count++;
// Pushing all the multiples of 'NUM' into the priority queue.
for (int i = 0; i < n; i++)
{
priorityQueue.push(num * primes[i]);
}
}
}
// Returning the Kth super ugly number.
return num;
}
int main()
{
// Taking user input.
int n, k;
cout << "Enter the size of the array primes: ";
cin >> n;
vector<int> primes(n + 1);
cout << "Enter the prime numbers: ";
for (int i = 0; i < n; i++){
cin >> primes[i];
}
cout << "Enter the kth super ugly number to be found: ";
cin >> k;
// Calling the function to find the Kth super ugly number.
cout << "The " << k << "th super ugly number is " << superUgly(primes, n, k) << endl;
return 0;
}
```

__Input__

__Input__```
Enter the size of the array primes:
3
Enter the prime numbers:
2 3 7
Enter the kth super ugly number to be found:
8
```

__Output__

__Output__`The 8th super ugly number is 9.`

**Time Complexity**

**Time Complexity**

* O(K * N * log N)*, where

*is the*

**K***super ugly number to be found, and*

**K**^{th}*is the size of the*

**N***array.*

**PRIMES[]**There are * 2* loops, one running from

*to*

**0***and the other running*

**N-1***times. The time taken to push into a priority queue is*

**K***, where*

**(log N)***is the number of elements already present in the priority queue.*

**N****Space Complexity**

**Space Complexity**

O(K), where K is the * K^{th}* super ugly number to be found.

This is because we store * K* super ugly numbers in the priority queue, which requires some space.