# K-th Ugly Ninja

Posted: 10 Apr, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

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