Super Ugly Numbers

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

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 queue, PRIORITY_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 K^th 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 K is the K^th 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 N is the number of elements already present in the priority queue.

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.