K-th Ugly Ninja
Ninja wants to hire some ugly ninjas in his team for doing ugly work. So he has made an array that contains primes integer ‘PRIME_ARR’.

Ninjas who are coming to audition have to take some random number and put it on their body and now Ninja will hire the ‘K-TH’ ugly ninja whose number has all prime factors in the array ‘PRIME_ARR’.

Your task is to help ninja in writing a code so he can find the ‘K-TH’ ugly ninja whose all prime factors are in the array ‘PRIME_ARR’.

You will be provided with the array ‘PRIME_ARR’ containing prime integers and an integer ‘K’.

Example :

Suppose given array ‘PRIME_ARR = { 2, 7, 13, 19 }’ and given number ‘K’ =12’ So the sequence of first ‘12’ ugly numbers is { 1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32 }. We start by filling ‘1’ and then ‘2’. We then fill ‘4’ as its prime factor 2 is present in ‘PRIME_ARR’. Then we fill ‘7’ and then ‘8’ as its prime factor ‘2’ is present in ‘PRIME_ARR’. Then insert '13'. Then ‘14’ as its prime factors ‘2’ and ‘7’ are present in ‘PRIME_ARR’. Then ‘16’ as its prime factor ‘2’ is present in ‘PRIME_ARR’. Then ‘19’. Then ‘26’ as its prime factors ‘2’ and ‘13’ are present in ‘PRIME_ARR’. Then ‘28’ as its prime factors ‘2’ and ‘7’ are present in ‘PRIME_ARR’. Then ‘32’ as its prime factor ‘2’ is present in ‘PRIME_ARR’. We don’t include ‘3’, ‘5’, ‘9’, ‘11’, and so on as their prime factors are not present in ‘PRIME_ARR’.

Input Format :

The first line of input contains a ‘T’ denoting the number of test cases. The first line of each test case contains two space-separated integers ‘N’ i.e size of the array ‘PRIME_ARR’ and the integer ‘K’. The second line of each test case contains an array ‘PRIME_ARR’ where ‘PRIME_ARR[i]’ denotes the ‘I-th’ prime integer.

Output Format :

For each test case, print an integer denoting the ‘KTH’ ugly number.

Note :

You do not need to print anything, It has already been taken care of. Just implement the function.

Constraints :

1

Question

K-th Ugly Ninja

Ninja wants to hire some ugly ninjas in his team for doing ugly work. So he has made an array that contains primes integer ‘PRIME_ARR’.

Ninjas who are coming to audition have to take some random number and put it on their body and now Ninja will hire the ‘K-TH’ ugly ninja whose number has all prime factors in the array ‘PRIME_ARR’.

Your task is to help ninja in writing a code so he can find the ‘K-TH’ ugly ninja whose all prime factors are in the array ‘PRIME_ARR’.

You will be provided with the array ‘PRIME_ARR’ containing prime integers and an integer ‘K’.

Example :

Suppose given array ‘PRIME_ARR = { 2, 7, 13, 19 }’ and given number ‘K’ =12’ 
So the sequence of first ‘12’ ugly numbers is { 1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32 }.
We start by filling ‘1’ and then ‘2’. We then fill ‘4’ as its prime factor 2 is present in ‘PRIME_ARR’.
Then we fill ‘7’  and then ‘8’ as its prime factor ‘2’ is present in ‘PRIME_ARR’.
Then insert '13'.
Then ‘14’ as its prime factors ‘2’ and ‘7’ are present in ‘PRIME_ARR’.
Then ‘16’ as its prime factor ‘2’ is present in ‘PRIME_ARR’.
Then ‘19’.
Then ‘26’ as its prime factors ‘2’ and ‘13’ are present in ‘PRIME_ARR’.
Then ‘28’ as its prime factors ‘2’ and ‘7’ are present in ‘PRIME_ARR’.
Then ‘32’ as its prime factor ‘2’ is present in ‘PRIME_ARR’.
We don’t include ‘3’, ‘5’, ‘9’, ‘11’, and so on as their prime factors are not present in ‘PRIME_ARR’.

Input Format :

The first line of input contains a ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers ‘N’ i.e size of the array ‘PRIME_ARR’ and the integer ‘K’.

The second line of each test case contains an array ‘PRIME_ARR’ where ‘PRIME_ARR[i]’ denotes the ‘I-th’ prime integer.

Output Format :

For each test case, print an integer denoting the ‘KTH’ ugly number.

Note :

You do not need to print anything, It has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 50
1 <= N <= 100
1 <= K <= 10 ^3
1 <= PRIME_ARR[i] <= 1000  

Time Limit: 1sec

Accepted Answer

Brute Approach

The idea here is to use the brute force approach and starting from ‘1’ find the ‘K’ ugly numbers till then remain in the loop.

Declare a set for super ugly numbers.
Insert the first ugly number into the set.
Initialize array ‘PRIME_OF[N]’ of size ‘N’ with 0. Each element of this array is an iterator for the corresponding prime in the ‘PRIME_ARR[N]’ array.
Initialize ‘ARR[i]’ array with ‘PRIME_ARR[N]’. This array behaves like next multiple variables of each prime in given ‘PRIME_ARR[N]’ array i.e; ‘ARR[i] = PRIME_ARR[I] * UGLY[++PRIME_OF[I]]’.
Now loop until there are ‘N’ elements in set ugly.
- Find minimum among current multiples of primes in ‘ARR’ array and insert it in the set of ‘UGLY’ numbers.
- Then find this current minimum is multiple of which prime
- Increase iterator by 1 i.e; ‘++PRIME_OF[i]’, for the next multiple of currently selected prime and update ‘ARR’ for it.

Space Complexity: O(n)Explanation:

O(K), where ‘K’ represents the ‘K-TH’ ugly number.

As we are using an ‘UGLY’ array for storing ‘K’ ugly numbers.

Time Complexity: O(n^2logn)Explanation:

O(N * log (N) * K), where ‘N’ is the size of the array and ‘K’ represents the ‘K-TH’ ugly number.

As for each number we have to check whether its prime factor is present in the ‘ARR’ array and as we are so insertion operation takes O(log (N)) time so overall complexity becomes equal to O(N *(log (N) * K)

Note: In python, we don't have a set so required ‘N’ time to insertion.

Java (SE 1.8)

/*

    Time complexity: O(N * log(N) * K)

    Space complexity: O(K) 



    Where N represents the size of array and K is K-th ugly Ninja.

*/



import java.util.ArrayList;

import java.util.Collections;

import java.util.TreeSet;



public class Solution 

{

    public static int uglyNinja(ArrayList primeArr, int n, int k) 

    {  

        

        int [] primes = new int[n];



        for (int i = 0; i < n; i++)

        {

            primes[i] = primeArr.get(i);

        }

        

        // Arr holds multiples of given primes.

        ArrayList arr = new ArrayList<>();

        for(int i=0 ; i        {

            arr.add(primes[i]);

        }



        // To store iterators of all primes.

        int [] primesOf = new int[n];

        for (int i = 0; i < n; i++)

        {

            primesOf[i] = 0;

        }



        // Create a set to store super ugly numbers.

        TreeSet ugly = new TreeSet<>();

        ugly.add(1);



        // loop until there are total n ugly numbers in set.

        while (ugly.size() != k)

        {

            /*

               Find minimum element among all current

               multiples of given prime.

            */

            int uglyNo = Collections.min(arr);



            // Insert this ugly number in set.

            ugly.add(uglyNo);



            /*

                loop to find current minimum is multiple

                Of which prime.

            */

            for (int j = 0; j < n; j++)

            {

                if (uglyNo == arr.get(j))

                {

                    primesOf[j]++;

                    int pos = 0;

                    for (int i = 1; i <= primesOf[j]; i++)

                    {

                        pos++;

                    }

                    int t = ugly.size(); 

                    Integer temp[] = new Integer[t]; 

                    temp = ugly.toArray(temp); 

                    arr.set(j, primes[j] * temp[pos]);

                    break;

                }

            }

        }

        return ugly.last();

    }

}

Python (3.5)

'''

    Time complexity: O(N * N * K)

    Space complexity: O(K) 



    Where N represents the size of array and K is K-th ugly Ninja. 

'''



from bisect import *



def uglyNinja(primeArr,  n,  k):



    primes = primeArr.copy()



    # Arr holds multiples of given primes

    arr = primes.copy()



    # To store iterators of all primes

    primesOf = [0]*n



    # Create a set to store super ugly numbers

    ugly = []



    insort(ugly, 1)



    # loop until there are total n ugly numbers in set

    while (len(ugly) != k):



        # Find minimum element among all current

        # multiples of given prime

        uglyNo = min(arr)



        # insert this ugly number in set



        # Check is uglyNo presnt in ugly



        idx = bisect_left(ugly, uglyNo)



        # If number is already in ugly arr then no need to insert again.

        if(idx < len(ugly) and ugly[idx] == uglyNo):



            # 'uglyNo' already present in 'ugly'.

            pass

        else:

            insort(ugly, uglyNo)



        # Loop to find current minimum is multiple of which prime

        for j in range(n):

            if (uglyNo == arr[j]):



                primesOf[j] += 1



                minElementIdx = 0



                for i in range(1, primesOf[j]+1):

                    minElementIdx += 1



                arr[j] = primes[j] * ugly[minElementIdx]



                break



    return ugly[-1]

C++ (g++ 5.4)

/*

    Time complexity: O(N * log(N) * K)

    Space complexity: O(K) 



    Where N represents the size of array and K is K-th ugly Ninja.

*/



int uglyNinja(vector primeArr, int n, int k)

{

    int primes[n];



    for (int i = 0; i < n; i++)

    {

        primes[i] = primeArr[i];

    }

    // Arr holds multiples of given primes.

    vector arr(primes, primes + n);



    // To store iterators of all primes.

    int primesOf[n];

    for (int i = 0; i < n; i++)

    {

        primesOf[i] = 0;

    }



    // Create a set to store super ugly numbers.

    set ugly;

    ugly.insert(1);



    // loop until there are total n ugly numbers in set.

    while (ugly.size() != k)

    {

        /*

            Find minimum element among all current

            multiples of given prime.

        */

        int uglyNo = *min_element(arr.begin(),

                                  arr.end());



        // Insert this ugly number in set.

        ugly.insert(uglyNo);



        /*

            loop to find current minimum is multiple

            Of which prime.

        */

        for (int j = 0; j < n; j++)

        {

            if (uglyNo == arr[j])

            {



                primesOf[j]++;

                set::iterator it = ugly.begin();



                for (int i = 1; i <= primesOf[j]; i++)

                {

                    it++;

                }



                arr[j] = primes[j] * (*it);

                break;

            }

        }

    }



    set::iterator it = ugly.end();

    it--;

    return *it;

}

Accepted Answer

Priority queue

The idea is to push the first ugly no. which is 1 into ‘PRIORITY_QUEUE’ and at every step take the top of priority_queue and push all the multiples of that top into priotiy_queue.

Firstly we declare a priority queue and pushed all the ‘PRIME_ARR’ array elements into the queue.
Now we run a loop until our priority queue size becomes equal to the ‘K’ and in every step, we find the min element from the heap.
- Suppose ‘PRIME_ARR[] = {2, 3, 5}’,
- Now our 1 is top so 1 is popped and 1 * 2, 1 * 3, 1 * 5 is pushed.
- At the second iteration, the min is 2, so it is popped and 2 * 2, 2 * 3, 2 * 5 is pushed, and so on.
Now we pushed all the multiples of that number in our priority queue.
In this way, we find the ‘K’ ugly number and return the ‘KTH’ ugly number as the answer.