K-th Ugly Ninja

PROBLEM STATEMENT

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

Approach 1

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.

Try Problem

Approach 2

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.

Try Problem