# 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.
• 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:

Code: