0781-0790

781. Rabbits in Forest $\star\star$

782. Transform to Chessboard $\star\star\star$

783. Minimum Distance Between BST Nodes $\star$

784. Letter Case Permutation $\star$

785. Is Graph Bipartite? $\star\star$

786. K-th Smallest Prime Fraction $\star\star\star$

 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
class Solution {
 public:
  vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {
    const int n = A.size();

    vector<int> ans = {0, 1};
    double l = 0;
    double r = 1;

    while (true) {
      double m = (l + r) / 2;
      ans[0] = 0;
      int count = 0;
      int j = 1;

      for (int i = 0; i < n; ++i) {
        while (j < n && A[i] > m * A[j]) ++j;
        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;
      else if (count > K)
        r = m;
      else
        return ans;
    }
  }
};

787. Cheapest Flights Within K Stops $\star\star$

788. Rotated Digits $\star$

789. Escape The Ghosts $\star\star$

790. Domino and Tromino Tiling $\star\star$