LeetCode 786: K-th Smallest Prime Fraction Solution

Master LeetCode problem 786 (K-th Smallest Prime Fraction), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

786. K-th Smallest Prime Fraction

Medium

Array Two Pointers Binary Search Sorting Heap (Priority Queue)

Problem Explanation

Explanation

To solve this problem, we can use a binary search approach. We can create a function to count the number of fractions less than or equal to a given value. Then, we perform binary search on the range of possible fractions to find the k-th smallest fraction.

Here are the steps:

Define a helper function to count the number of fractions less than or equal to a given value.
Initialize two variables left and right to represent the range of fractions we are searching in. left will be the minimum possible fraction (0/1) and right will be the maximum possible fraction (1/1).
Perform binary search on the range [left, right] to find the k-th smallest fraction.
Within each iteration of binary search, calculate the mid fraction (left + right) / 2.
Use the helper function to count the number of fractions less than or equal to the mid fraction.
Adjust the range [left, right] based on the count to move towards the k-th smallest fraction.

The time complexity of this approach is O(n * log(max - min)), where n is the number of elements in the array and max - min is the range of possible fractions.

Solution Code

class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int n = arr.length;
        double left = 0, right = 1;
        
        while (left < right) {
            double mid = (left + right) / 2;
            int count = countFractions(arr, mid);
            
            if (count < k) {
                left = mid;
            } else {
                right = mid;
            }
        }
        
        double res = 0;
        int[] result = new int[2];
        
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                double fraction = (double) arr[i] / arr[j];
                if (fraction >= left && fraction <= right) {
                    res = Math.max(res, fraction);
                    if (res == right) {
                        result[0] = arr[i];
                        result[1] = arr[j];
                        break;
                    }
                }
            }
        }
        
        return result;
    }
    
    private int countFractions(int[] arr, double mid) {
        int count = 0;
        int n = arr.length;
        
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                double fraction = (double) arr[i] / arr[j];
                if (fraction <= mid) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 786 (K-th Smallest Prime Fraction)?

This page provides optimized solutions for LeetCode problem 786 (K-th Smallest Prime Fraction) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 786 (K-th Smallest Prime Fraction)?

The time complexity for LeetCode 786 (K-th Smallest Prime Fraction) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 786 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 786 in Java, C++, or Python.

Back to LeetCode Solutions