Last Updated: 9 Apr, 2021
K-th Smallest Prime Fraction
Moderate
Asked in company
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
Approaches
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.
The main idea is to use a priority queue ‘QUE’ which stores the value of the fraction and the indices of elements that contribute to that fraction. The priority queue sorts the value based on the fraction values in ascending order. Pop the top K values and add values that are greater than the current value of the fraction. After K, such iteration, the top value will be our answer.
- Maintain a priority queue ‘QUE’ that at every node stores a vector :
- the fraction value that is ARR[i] / ARR[j] where ‘i’ and ‘j’ and indices and ‘i’ < ‘j’.
- ARR[i].
- ARR[j].
- Initially add N values where all ‘i’ from 0 to ‘N - 1’ is the numerator but have a common denominator the value at ‘N - 1’th index, i.e., ARR[N - 1].
- While ‘K’ is greater than 1:
- Pop of the top Node.
- The top node ‘TOPNODE’ contains fraction value and index ‘i’, which denotes numerator, and ‘j,’ which denotes denominator.
- Reduce ‘j’ by 1.
- Push back in the node :
- Fraction value with ARR[i] / ARR[j]
- ‘i’ the element which is the numerator.
- ‘j’ the element which is the denominator.
- Reduce ‘K’ by 1.
- The top node now is our result.
- Maintain an array ‘RES’ which contains the final result.
- Pop the top node :
- The ‘TOPNODE’[1] contains the index of the numerator, therefore push ARR[‘TOPNODE’[1]] in ‘res’.
- The ‘TOPNODE’[2] contains the index of the denominator, therefore push ARR[‘TOPNODE’[2]] in ‘res’
- Return ‘RES’ as the final answer.