Skip to content

786. K-th Smallest Prime Fraction 👍

  • Time: $O(n\log \max^2(A))$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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