K-th Ugly Ninja

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
1 upvote
Asked in companies
OYOMathworks

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’.
Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
4 12
2 3 5 7
2 5
2 5

Sample Output 1 :

14
8

Explanation Of Sample Input 1 :

Test Case 1:

For the first test case given ‘PRIME_ARR’ is { 2, 3, 5, 7 } so the sequence of first ‘12’ ugly numbers is { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14 } so we return ‘14’ as the answer.

Test Case 2:

For this test case given ‘PRIME_ARR’ is { 2, 5 } so the sequence of first ‘5’ ugly numbers is {1, 2, 4, 5, 8 } so we return ‘8’ as our answer.

Sample Input 2 :

2
3 1
2 3 5
5 9
3 5 7 11 13

Sample Output 2 :

1
21
Hint

Can you check each and every number until you find ‘K’ ugly numbers?

Approaches (2)
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.
Time Complexity

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.

Space Complexity

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

 

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

Code Solution
(100% EXP penalty)
K-th Ugly Ninja
Full screen
Console