# Leetcode 786 - K-th smallest prime fraction

`Note:`

- Use built-in
`MinPriorityQueue`

whose priority is based on`arr[i] / arr[j]`

. - We don’t need to add all combinations of
`arr[i] / arr[j]`

at once. - Add all
`arr[0] / arr[j]`

first, and`arr[0] / arr[N - 1]`

has the highest priority. - After dequeuing it, who’s gonna be the next?
- Either one of the left, or
`arr[i + 1] / arr[j]`

. - We are pretty sure that
`arr[i + 1] / arr[j]`

has a higher priority than those unadded because`arr[i + 1]`

is the smallest number among unadded, plus`arr[j]`

is the biggest number.

- Either one of the left, or
- Do this K times and we’ve found the answer.

`Question:`

You are given a `sorted`

integer array arr containing `1`

and `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 < arr.length`

, we consider the fraction `arr[i] / arr[j]`

.

Return the `kth`

smallest fraction considered. Return your answer as an array of integers of size 2, where `answer[0] == arr[i]`

and `answer[1] == arr[j]`

.

`Example:`

1 | Input: arr = [1,2,3,5], k = 3 |

`Code:`

1 | /** |