K-th Smallest Prime Fraction

Posted: 9 Apr, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.

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
Approach 1

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.
Try Problem