K-th Smallest Prime Fraction

Moderate

0/80

Average time to solve is 30m

1 upvote

Asked in company

Problem statement

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

Print the Kth smallest fraction considered. Print your answer as an array of integers of size 2, where ANSWER[0] == ARR[i] and ANSWER[1] == 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.

Detailed explanation ( Input/output format, Notes, Images )

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 :

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 :

Sample Output 2 :

1 5 
3 11

Hint 1

Hint 2

Can we use sorting?

Approaches (2)

Approach 1

Approach 2

Sorting The Pairs

The main idea is to find all fractions of all pairs of elements in the array and sort them, then return the ‘Kth’ smallest element, which will be at the (K - 1)th index.

Make a ‘FRACTIONS’ array which is an array of arrays and contains exactly 3 values :
- the fraction value that is ARR[i] / ARR[j] where ‘i’ and ‘j’ and indices and ‘i’ < ‘j’.
- ARR[i].
- ARR[j].
Sort the ‘FRACTIONS’ based on the first index, which contains the fraction value.
Make a ‘RES’ array that has the final result.
Push the 2nd and 3rd elements of the ‘K - 1’th index of the ‘FRACTIONS’ array.
Return the ‘RES’ as the final result.

Time Complexity

O((N ^ 2) * log(N ^ 2)), where ‘N’ is the length of the given array.

For an array with ‘N’ elements, N * (N - 1) / 2 pairs can be formed, and we are sorting all pairs of values. Therefore, the net time complexity will be O((N ^ 2) * log(N ^ 2)).

Space Complexity

O(N ^ 2).

Since we are storing fractions for each pair so overall space complexity will be O(N ^ 2).

(100% EXP penalty)

K-th Smallest Prime Fraction

Console