1

K-th Smallest Prime Fraction

Difficulty: MEDIUM
Avg. time to solve
30 min
Success Rate
65%

Problem Statement
Suggest Edit

You are given a sorted integer array/lst 'ARR' containing prime numbers, where all the integers of ‘ARR’ are unique. You are also given an integer ‘K’.

For every ‘i’ and ‘j’ where 0 <= i < j < N where ‘N’ is the length of the array, we consider the fraction ARR[i] / ARR[j].

Note :

A prime number is a number that has only two unique factors, one and the number itself. E.g., 3 has only 2 factors, 1 and 3 itself.

For example :

Given ‘N’ = 4, ‘K’ = 2, ‘ARR’[] = 1, 2, 3, 5
The answer is 1 and 3 because :
½ = 0.50
⅓ = 0.33
⅕ = 0.20
⅔ = 0.66
⅖ = 0.40
⅗ = 0.60
Therefore the 2nd smallest value is 0.33 therfore 1 and 3 is the answer.

Input Format :

The first line of input contains an integer ‘T’ denoting the number of test cases. The 'T' test cases follow.

The first line of each test case contains 2 space-separated integers, ‘N’ and ‘K,’ where ‘N’ is the number of elements of the array, and you have to tell the fraction that makes the ‘K’th smallest fraction.

The second line of each test case contains ‘N’ space-separated integers, denoting the array elements.

Output Format :

For each test case, print two integers denoting numerator and denominator respectively of the smallest fraction.

The output of each test case will be printed in a separate line.

Note :

You don’t need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5
1 <= N <= 1000
1 <= K <= (N) * (N - 1) / 2
1 <= ARR[ i ] <= 10 ^ 4

Where 'ARR[i]' denotes the 'ith' element of ARR.

Time limit: 1 sec
Sample Input 1 :
2
4 2
1 2 3 5
4 6
5 7 11 13
Sample Output 1 :
1 3 
11 13
Explanation of Sample Input 1 :
For the first test case:
The answer is 1 and 3 because :
1 / 2  = 0.50
1 / 3  = 0.33
1 / 5  = 0.20
2 / 3  = 0.66
2 / 5  = 0.40
3 / 5  = 0.60
Therefore the 2nd smallest value is 0.33 1, and 3 is the answer.


For the second test case:
The answer is 1 and 3 because :
5 / 7 = 0.71
5 / 11 = 0.45
5 / 13 = 0.38
7 / 11 = 0.63
7 / 13 = 0.53
11 / 13 = 0.84
Therefore the 6th smallest value is 0.84 therefore 11 and 13 is the answer.    
Sample Input 2 :
2
4 1
1 2 3 5
5 2
2 3 5 7 11
Sample Output 2 :
1 5 
3 11
Reset Code
Full screen
copy-code
Console