# Super Ugly Numbers

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

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

__Dynamic Programming__

__Dynamic Programming__

__Algorithm__

__Algorithm__- Declare a dp array whose value at ith index,
is representing the**DP[i]**super ugly number**i**^{th} - Initially, set
(for all**DP[i] = 1**)**0 <= i<= K+1** - Create a pointer array of size
(size of the primes array) where**N**represents the**pointer[i]**prime number in the given array.**i**^{th} - Set
(for all**pointer[i] = 1****0 <= i< N)** - We will run a loop for
to**i = 2****i = N.**

- To get the ith super ugly number at the ith position of the
array, we find the minimum value of the**DP**index of the dp array by running the following loop in the range**i**^{th}to**0**, and storing it in a variable**N - 1**, to keep track of the answer.**MI**

**DP[pointer[j]] * primes[j].**

is updated with the minimum value.**DP[i]**- Iterate through the pointer array, increasing the value of those indices whose value is equal to the minimum value by one.

* DP[K] *will provide us with the

*ugly number.*

**K**^{th}Confused??? It will become clear after going through the example:

__Example__

__Example__

**N = 2**

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

**K = 3**

Let’s consider our DP array:

**i = 2**

**MI = INT_MAX**

** j = 0**

**TEMP = DP[POINTER[0]] * PRIMES[0]**

** = DP[1] * 2**

** = 1 * 2**

** = 2**

**MI = MIN(MI, TEMP)**

** = MIN(INT_MAX, 2)**

** = 2**

** j = 1**

**TEMP = DP[POINTER[1]] * PRIMES[1]**

** = DP[1] * 3**

** = 1 * 3**

** = 3**

**MI = MIN(MI, TEMP)**

** = MIN(2, 3)**

** = 2**

**DP[2] = 2**

** j = 0**

**TEMP = DP[POINTER[0]] * PRIMES[0]**

**= DP[1] * 2**

**= 1 * 2**

**= 2**

**MI = 2**

Thus, **POINTER[0] = 2**

** j = 1**

**TEMP = DP[POINTER[1]] * PRIMES[1]**

** = DP[1] * 3**

** = 1 * 3**

** = 3**

**MI = 2**

Thus, **POINTER[1] = 1**

**i = 3**

**MI = INT_MAX**

** j = 0**

**TEMP = DP[POINTER[0]] * PRIMES[0]**

** = DP[1] * 2**

** = 2 * 2**

** = 4**

**MI = MIN(MI, TEMP)**

** = MIN(INT_MAX, 4)**

** = 4**

** j = 1**

**TEMP = DP[POINTER[1]] * PRIMES[1]**

** = DP[1] * 3**

** = 1 * 3**

** = 3**

**MI = MIN(MI, TEMP)**

** = MIN(4, 3)**

** = 3**

**DP[3] = 3**

** j = 0**

**TEMP = DP[POINTER[0]] * PRIMES[0]**

**= DP[1] * 2**

**= 2 * 2**

**= 4**

**MI = 3**

Thus, **POINTER[0] = 2**

**j = 1**

**TEMP = DP[POINTER[1]] * PRIMES[1]**

** = DP[1] * 3**

** = 1 * 3**

** = 3**

**MI = 3**

Thus, **POINTER[1] = 2**

Thus, the * 3^{rd}* super ugly number is

*.*

**3**

**Implementation**

**Implementation**

__Program__

__Program__```
// C++ program to find super ugly numbers using dynamic programming.
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
// Function to return the Kth super ugly number.
int superUgly(vector<int> & primes, int n, int k)
{
// Initialising the dp array of size k+1 with 1.
vector<long long> dp(k + 1, 1);
// Initialising a vector 'pointer' of size n with 1.
vector<int> pointer(n, 1);
// Checking for the kth super ugly number.
for (int i = 2; i <= k; i++)
{
long long mi = INT_MAX;
for (int j = 0; j < n; j++)
{
long long temp = dp[pointer[j]] * primes[j];
mi = min(mi, temp);
}
// Initialising the dp array with the minimum super ugly number.
dp[i] = mi;
// Loop for incrementing the pointers.
for (int j = 0; j < n; j++)
{
long long temp = dp[pointer[j]] * primes[j];
if (temp == mi)
{
pointer[j]++;
}
}
}
// Returning the kth super ugly number.
return dp[k];
}
int main()
{
// Taking user input.
int n, k, a;
cout << "Enter the size of the array primes: ";
cin >> n;
vector<int> primes;
cout << "Enter the prime numbers: ";
for (int i = 0; i < n; i++)
{
cin >> a;
primes.push_back(a);
}
cout << "Enter the k-th 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**

The time complexity is given by **O(N*K).**

This is because there are * 2* nested loops, first from

*to*

**2***and the other from*

**K***to*

**0**

**N-1.****Space Complexity**

**Space Complexity**

The space complexity is given by * O(N+K)*.

This is because we take * 2 *extra arrays to find the

*super ugly number, one of size*

**K**^{th }*and the other of size*

**N**

**K.**__Key Takeaways__

__Key Takeaways__

So, this blog discussed the problem of Super Ugly Numbers and shed some light on its time and space complexity.

To learn more, head over right now to* ** CodeStudio* to practice problems on prime numbers and their different variations and crack your interviews like a Ninja!

Practicing a bunch of questions is not enough in this competitive world. So go check out where you stand among your peers by taking our __mock tests__* *and see which areas need improvement.

In case of any comments or suggestions, feel free to post them in the comments section.

Comments

## No comments yet

## Be the first to share what you think