K-th Ugly Ninja

Posted: 10 Apr, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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