Sponsored
Sponsored
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.
Time Complexity: O(n^2 log(n^2))
Space Complexity: O(n^2)
1#include <stdio.h>
2#include <stdlib.h>
3
4typedef struct {
5 double value;
6 int numerator;
7 int denominator;
8} Fraction;
9
10int cmp(const void* a, const void* b) {
11 Fraction* fa = (Fraction*)a;
12 Fraction* fb = (Fraction*)b;
13 return (fa->value > fb->value) - (fa->value < fb->value);
14}
15
16int* kthSmallestPrimeFraction(int* arr, int arrSize, int k, int* returnSize){
17 Fraction* fractions = (Fraction*)malloc(arrSize * arrSize * sizeof(Fraction));
18 int index = 0;
19 for (int i = 0; i < arrSize; ++i) {
20 for (int j = i + 1; j < arrSize; ++j) {
21 fractions[index].value = (double)arr[i] / arr[j];
22 fractions[index].numerator = arr[i];
23 fractions[index].denominator = arr[j];
24 ++index;
25 }
26 }
27 qsort(fractions, index, sizeof(Fraction), cmp);
28 int* result = (int*)malloc(2 * sizeof(int));
29 result[0] = fractions[k - 1].numerator;
30 result[1] = fractions[k - 1].denominator;
31 *returnSize = 2;
32 free(fractions);
33 return result;
34}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.
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.
Time Complexity: O(n log(max_fraction))
Space Complexity: O(1)
1
Utilizing JavaScript, binary search reduces the possible range for fraction values. A two-pointer setup helps count smaller fractions, determining bounds for pinpointing the k-th smallest fraction.