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>& A, int K) {
    const int n = A.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. A[i] / A[j] <= m,
      // so fractionsNoGreaterThanM for index i will be n - j
      for (int i = 0, j = 1; i < n; ++i) {
        while (j < n && A[i] > m * A[j])
          ++j;
        if (j == n)
          break;
        fractionsNoGreaterThanM += n - j;
        if (p * A[j] < q * A[i]) {
          p = A[i];
          q = A[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[] A, int K) {
    final int n = A.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. A[i] / A[j] <= m,
      // so fractionsNoGreaterThanM for index i will be n - j
      for (int i = 0, j = 1; i < n; ++i) {
        while (j < n && A[i] > m * A[j])
          ++j;
        if (j == n)
          break;
        fractionsNoGreaterThanM += n - j;
        if (p * A[j] < q * A[i]) {
          p = A[i];
          q = A[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, A: List[int], K: int) -> List[int]:
    n = len(A)
    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 A[i] > m * A[j]:
          j += 1
        count += n - j
        if j == n:
          break
        if ans[0] * A[j] < ans[1] * A[i]:
          ans[0] = A[i]
          ans[1] = A[j]

      if count < K:
        l = m
      elif count > K:
        r = m
      else:
        return ans