786. K-th Smallest Prime Fraction LeetCode Solution

In this guide, you will get 786. K-th Smallest Prime Fraction LeetCode Solution with the best time and space complexity. The solution to K-th Smallest Prime Fraction problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
K-th Smallest Prime Fraction solution in C++
K-th Smallest Prime Fraction solution in Java
K-th Smallest Prime Fraction solution in Python
Additional Resources

786. K-th Smallest Prime Fraction LeetCode Solution image

Problem Statement of 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] 0.
All the numbers of arr are unique and sorted in strictly increasing order.
1 <= k <= arr.length * (arr.length – 1) / 2

Follow up: Can you solve the problem with better than O(n2) complexity?

Complexity Analysis

Time Complexity: O(n\log \max^2(A))
Space Complexity: O(1)

786. K-th Smallest Prime Fraction LeetCode Solution in C++

class Solution {
 public:
  vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
    const int n = arr.size();
    double l = 0.0;
    double r = 1.0;

    while (l < r) {
      const double m = (l + r) / 2.0;
      int fractionsNoGreaterThanM = 0;
      int p = 0;
      int q = 1;

      // For each index i, find the first index j s.t. arr[i] / arr[j] <= m,
      // so fractionsNoGreaterThanM for index i will be n - j.
      for (int i = 0, j = 1; i < n; ++i) {
        while (j < n && arr[i] > m * arr[j])
          ++j;
        if (j == n)
          break;
        fractionsNoGreaterThanM += n - j;
        if (p * arr[j] < q * arr[i]) {
          p = arr[i];
          q = arr[j];
        }
      }

      if (fractionsNoGreaterThanM == k)
        return {p, q};
      if (fractionsNoGreaterThanM > k)
        r = m;
      else
        l = m;
    }

    throw;
  }
};
/* code provided by PROGIEZ */

786. K-th Smallest Prime Fraction LeetCode Solution in Java

class Solution {
  public int[] kthSmallestPrimeFraction(int[] arr, int k) {
    final int n = arr.length;
    double l = 0.0;
    double r = 1.0;

    while (l < r) {
      final double m = (l + r) / 2.0;
      int fractionsNoGreaterThanM = 0;
      int p = 0;
      int q = 1;

      // For each index i, find the first index j s.t. arr[i] / arr[j] <= m,
      // so fractionsNoGreaterThanM for index i will be n - j.
      for (int i = 0, j = 1; i < n; ++i) {
        while (j < n && arr[i] > m * arr[j])
          ++j;
        if (j == n)
          break;
        fractionsNoGreaterThanM += n - j;
        if (p * arr[j] < q * arr[i]) {
          p = arr[i];
          q = arr[j];
        }
      }

      if (fractionsNoGreaterThanM == k)
        return new int[] {p, q};
      if (fractionsNoGreaterThanM > k)
        r = m;
      else
        l = m;
    }

    throw new IllegalArgumentException();
  }
}
// code provided by PROGIEZ

786. K-th Smallest Prime Fraction LeetCode Solution in Python

class Solution:
  def kthSmallestPrimeFraction(self, arr: list[int], k: int) -> list[int]:
    n = len(arr)
    ans = [0, 1]
    l = 0
    r = 1

    while True:
      m = (l + r) / 2
      ans[0] = 0
      count = 0
      j = 1

      for i in range(n):
        while j < n and arr[i] > m * arr[j]:
          j += 1
        count += n - j
        if j == n:
          break
        if ans[0] * arr[j] < ans[1] * arr[i]:
          ans[0] = arr[i]
          ans[1] = arr[j]

      if count < k:
        l = m
      elif count > k:
        r = m
      else:
        return ans
 # code by PROGIEZ