You are given a sorted integer array arr containing 1 and prime numbers, where all the integers of arr are unique. You are also given an integer k.
For every i and j where 0 <= i < j < arr.length, we consider the fraction arr[i] / arr[j].
Return the kth smallest fraction considered. Return your answer as an array of integers of size 2, where answer[0] == arr[i] and answer[1] == arr[j].
Example 1:
Input: arr = [1,2,3,5], k = 3 Output: [2,5] Explanation: The fractions to be considered in sorted order are: 1/5, 1/3, 2/5, 1/2, 3/5, and 2/3. The third fraction is 2/5.
Example 2:
Input: arr = [1,7], k = 1 Output: [1,7]
Constraints:
2 <= arr.length <= 10001 <= arr[i] <= 3 * 104arr[0] == 1arr[i] is a prime number for i > 0.arr are unique and sorted in strictly increasing order.1 <= k <= arr.length * (arr.length - 1) / 2Follow up: Can you solve the problem with better than
O(n2) complexity?This approach uses a min-heap to efficiently find the kth smallest fraction. By iterating through each pair of elements (i, j) in the array where i < j, we can calculate the fraction arr[i]/arr[j] and push it into the heap. The heap is then used to retrieve the k-th smallest element efficiently.
In this C solution, a struct called 'Fraction' is defined to represent a fraction along with its value. The input array is iterated over pairs of indices to compute the fractions which are stored in an array. The array is then sorted based on the fraction values using the quicksort method. Finally, the k-th smallest fraction is returned.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2 log(n^2))
Space Complexity: O(n^2)
This approach uses binary search on the value of fractions. By implementing a search over the potential range of fraction values, the algorithm counts how many fractions are less than a given mid-point, narrowing down to the k-th one by manipulating the bounds of the potential fraction values. A two-pointer technique helps count the fractions efficiently.
This C code performs binary searching over the range of fraction values. To find the k-th smallest fraction, the algorithm counts fractions with a value less than a target using two pointers, refining the bounds until the count reaches k.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log(max_fraction))
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Heap Approach | Time Complexity: O(n^2 log(n^2)) |
| Binary Search on the Value | Time Complexity: O(n log(max_fraction)) |
Kth Largest Element in an Array - Quick Select - Leetcode 215 - Python • NeetCode • 331,616 views views
Watch 9 more video solutions →Practice K-th Smallest Prime Fraction with our built-in code editor and test cases.
Practice on FleetCode