Algorithm


Problem Name: 786. K-th Smallest Prime Fraction

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
Output: [2,5]
Explanation: The fractions to be considered in sorted order are:
1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.
The third fraction is 2/5.

Example 2:

Input: arr = [1,7], k = 1
Output: [1,7]

 

Constraints:

  • 2 <= arr.length <= 1000
  • 1 <= arr[i] <= 3 * 104
  • arr[0] == 1
  • arr[i] is a prime number for i > 0.
  • All the numbers of arr are unique and sorted in strictly increasing order.
  • 1 <= k <= arr.length * (arr.length - 1) / 2

Code Examples

#1 Code Example with Javascript Programming

Code - Javascript Programming


const kthSmallestPrimeFraction = function(A, K) {
  let ans = []
  let left = 0.0
  let right = 1.0
  while (right - left > 1e-9) {
    const mid = left + (right - left) / 2
    const { count, p, q } = maxUnder(mid, A)
    if (count >= K) {
      ans = [p, q]
      right = mid
    } else {
      left = mid
    }
  }
  return ans

  function maxUnder(x, primes) {
    let [p, q] = [0, 1]
    let count = 0
    let l = -1
    for (let r = 1; r  <  primes.length; r++) {
      while (primes[l + 1] < primes[r] * x) {
        l += 1
      }
      count += l + 1
      if (l >= 0 && p * primes[r] < q * primes[l]) {
        ;[p, q] = [primes[l], primes[r]]
      }
    }
    return { count, p, q }
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
arr = [1,2,3,5], k = 3

Output

x
+
cmd
[2,5]

#2 Code Example with Python Programming

Code - Python Programming


class Solution:
    def kthSmallestPrimeFraction(self, A, K):
        heap, used = [(A[0] / A[-1], 0, len(A) - 1)], {(0, len(A) - 1)}
        for i in range(K):
            try:
                cur, l, r = heapq.heappop(heap)
                used.add((l, r))
                if (l + 1, r) not in used:
                    heapq.heappush(heap, (A[l + 1] / A[r], l + 1, r))
                    used.add((l + 1, r))
                if (l, r - 1) not in used:
                    heapq.heappush(heap, (A[l] / A[r - 1], l, r - 1))
                    used.add((l, r - 1))
            except:
                break
        return [A[l], A[r]]
Copy The Code & Try With Live Editor

Input

x
+
cmd
arr = [1,2,3,5], k = 3

Output

x
+
cmd
[2,5]
Advertisements

Demonstration


Previous
#785 Leetcode Is Graph Bipartite? Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#787 Leetcode Cheapest Flights Within K Stops Solution in C, C++, Java, JavaScript, Python, C# Leetcode