Super Ugly Numbers

Ishita Chawla
Last Updated: May 13, 2022

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

You are given an array, PRIMES[], consisting of ‘N’ prime numbers. A super ugly number is one whose prime factors lie in this array PRIMES[]. Your task is to find the Kth super ugly number.

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

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

Example

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

Algorithm

  • We use a min-heap priority queuePRIORITY_QUEUE,  to store the elements in ascending order.
  • First, we insert the elements of the PRIMES[] array into the priority queue. 
  • 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 PRIMES[] array and push it into the priority queue. 
  • When the count becomes equal to K, we will store the result and return it. In this way, we will get the Kth super ugly number quite easily.

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 PRIMES into the PRIORITY_QUEUE.

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

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

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

The 8th super ugly number is 9.

Time Complexity

O(K * N * log N), where is the Kth super ugly number to be found, and N is the size of the PRIMES[] array.

There are 2 loops, one running from 0 to N-1 and the other running K times. The time taken to push into a priority queue is (log N), where is the number of elements already present in the priority queue.

Space Complexity

O(K), where K is the Kth 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

Algorithm

  • Declare a dp array whose value at ith index, DP[i] is representing the ith super ugly number 
  • Initially, set DP[i] = 1 (for all 0 <= i<= K+1)
  • Create a pointer array of size (size of the primes array) where pointer[i] represents the ith prime number in the given array.
  • Set pointer[i] = 1 (for all 0 <= i< N)
  • We will run a loop for i = 2 to i = N.
  • To get the ith super ugly number at the ith position of the DP array, we find the minimum value of the ith index of the dp array by running the following loop in the range to N - 1, and storing it in a variable MI, to keep track of the answer.

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

  • DP[i] is updated with the minimum value.
  • 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 Kth ugly number.

Confused??? It will become clear after going through the 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 3rd super ugly number is 3.

 

Implementation

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

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

The 8th super ugly number is 9.

 

Time Complexity

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

This is because there are 2 nested loops, first from 2 to K and the other from 0 to N-1. 

Space Complexity

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

This is because we take extra arrays to find the Kth super ugly number, one of size and the other of size K.

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.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think