leetcode

commit 5f258ef57fc3afb89a357d5cac2027156a56c034
parent b2c8b0357da884fdb63366fd0605a1f5cb15832f
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 10 May 2024 18:50:23 +0200

Daily Problem

Diffstat:
A
Problems/0786.cpp
 | 
19
+++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 20 insertions(+), 0 deletions(-)
diff --git a/Problems/0786.cpp b/Problems/0786.cpp
@@ -0,0 +1,19 @@
+class Solution {
+  public:
+    vector<int> kthSmallestPrimeFraction(const vector<int> &arr, int k) const {
+        priority_queue<tuple<double, int, int>> pq;
+
+        for (int i = 0; i < arr.size(); i++) {
+            pq.emplace(-1.0 * arr[i] / arr.back(), i, arr.size() - 1);
+        }
+
+        while (true) {
+            auto [_, i, j] = pq.top();
+            pq.pop();
+            if (!--k) return {arr[i], arr[j]};
+            if (--j > i) pq.emplace(-1.0 * arr[i] / arr[j], i, j);
+        }
+
+        return {};
+    }
+};
diff --git a/README.md b/README.md
@@ -484,6 +484,7 @@ for solving problems.
 |  0783  |    Easy    | [Minimum Distance Between BST Nodes](Problems/0783.cpp)                                            |
 |  0784  |   Medium   | [Letter Case Permutation](Problems/0784.cpp)                                                       |
 |  0785  |   Medium   | [Is Graph Bipartite?](Problems/0785.cpp)                                                           |
+|  0786  |   Medium   | [K-th Smallest Prime Fraction](Problems/0786.cpp)                                                  |
 |  0787  |   Medium   | [Cheapest Flights Within K Stops](Problems/0787.cpp)                                               |
 |  0788  |   Medium   | [Rotated Digits](Problems/0788.cpp)                                                                |
 |  0789  |   Medium   | [Escape The Ghosts](Problems/0789.cpp)                                                             |