../ Competitive Programming

-rw-r--r--aguang1.7 KiB2024-05-102 min read

Leet Code Daily 2024-05-10 - K-th Smallest Prime Fraction

Description

Solution

Monotonicity Optimization

First, let's define:

F(x, y) = \lvert \{ \frac{A_{i}}{A_j} \text{ } \lvert \text{ } 0 \leq i \lt j \lt n \land \frac{A_{i}}{A_j} \leq \frac{A_x}{A_y} \} \rvert

We know that for any $\frac{A_x}{A_y}$ , we can compute $F(x, y)$ in $O(n)$ time.

Binary Search

Then we can enumerate x, and for each x, binary search:

\argmax_{y}{F(x, y) \geq k}

Time Complexity

O(n^2 \times \log_2{n})

Note

There might be some more efficient solution.

Code

c++

class Solution {
public:
    bool fracCmp(int x1, int y1, int x2, int y2) { return x1 * y2 <= x2 * y1; }

    int fracCnt(const vector<int>& arr, int x, int y) {
        int ret = 0;
        for (int i = 0, j = 1; i + 1 < arr.size(); i++) {
            while (j < arr.size() &&
                   (j <= i || !fracCmp(arr[i], arr[j], arr[x], arr[y]))) {
                j++;
            }
            ret += arr.size() - j;
        }
        return ret;
    }

    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
        for (int x = 0; x + 1 < arr.size(); x++) {
            int ly = x + 1, hy = arr.size() - 1;
            while (ly < hy) {
                int my = (ly + hy) / 2 + 1;
                if (fracCnt(arr, x, my) >= k) {
                    ly = my;
                } else {
                    hy = my - 1;
                }
            }
            if (fracCnt(arr, x, ly) == k) {
                return vector<int>{ arr[x], arr[ly] };
            }
        }
        return vector<int>{ arr[0], arr[1] };
    }
};

press any key / click to skip