Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 10 Apr, 2021

Moderate

```
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’.
```

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

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

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

```
1 <= T <= 50
1 <= N <= 100
1 <= K <= 10 ^3
1 <= PRIME_ARR[i] <= 1000
Time Limit: 1sec
```

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.

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.