K-th Smallest Prime Fraction - Practice Coding Problems

K-th Smallest Prime Fraction - Problem

Array Two Pointers Binary Search Sorting Heap (Priority Queue) Medium

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 k-th smallest fraction considered. Return your answer as an array of integers of size 2, where answer[0] == arr[i] and answer[1] == arr[j].

Input & Output

Example 1 — Basic Case

$ Input: arr = [1,2,3,5], k = 3

› Output: [2,5]

💡 Note: All fractions: 1/2, 1/3, 1/5, 2/3, 2/5, 3/5. Sorted: 1/5, 1/3, 2/5, 1/2, 3/5, 2/3. The 3rd smallest is 2/5.

Example 2 — Different K Value

$ Input: arr = [1,7], k = 1

› Output: [1,7]

💡 Note: Only one fraction possible: 1/7, so the 1st smallest is 1/7.

Example 3 — Larger Array

$ Input: arr = [1,2,3,5,7], k = 4

› Output: [1,2]

💡 Note: Many fractions possible. After sorting, the 4th smallest fraction is 1/2.

Constraints

2 ≤ arr.length ≤ 1000
1 ≤ arr[i] ≤ 3 × 10⁴
arr[0] == 1
arr[i] is a prime number for i > 0
All the numbers of arr are unique and sorted in ascending order
1 ≤ k ≤ arr.length × (arr.length - 1) / 2

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted array [1,2,3,5] and k=3

Generate

All possible fractions: 1/2, 1/3, 1/5, 2/3, 2/5, 3/5

Sort

Sorted fractions: 1/5, 1/3, 2/5, 1/2, 3/5, 2/3

Output

3rd smallest fraction: [2,5]

Key Takeaway

🎯 Key Insight: Use binary search on fraction values to efficiently find the k-th smallest without generating all fractions

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is that we need to find the k-th smallest fraction efficiently from all possible pairs. The binary search on answer space approach is optimal with O(n log W) time complexity, where we binary search on fraction values and count how many fractions are smaller than each candidate value.

Common Approaches

Approach	Time	Space	Notes
✓ Generate All Fractions and Sort	O(n² log n)	O(n²)	Generate all possible fractions, sort them, and return the k-th smallest
Priority Queue (Min Heap)	O(k log n)	O(n)	Use a min heap to efficiently find the k smallest fractions without generating all
Binary Search on Answer Space	O(n log W)	O(1)	Binary search on fraction values to find the k-th smallest fraction efficiently

Generate All Fractions and Sort — Algorithm Steps

Generate all fractions with their indices
Sort fractions by their decimal values
Return the k-th fraction's numerator and denominator

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all fractions arr[i]/arr[j] where i < j

Sort

Sort fractions by their decimal values

Select

Pick the k-th smallest fraction

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    double value;
    int num;
    int den;
} Fraction;

int compare(const void *a, const void *b) {
    Fraction *fa = (Fraction *)a;
    Fraction *fb = (Fraction *)b;
    if (fa->value < fb->value) return -1;
    if (fa->value > fb->value) return 1;
    return 0;
}

void solution(int *arr, int n, int k, int *result) {
    Fraction *fractions = malloc(n * n * sizeof(Fraction));
    int count = 0;
    
    // Generate all fractions
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            fractions[count].value = (double)arr[i] / arr[j];
            fractions[count].num = arr[i];
            fractions[count].den = arr[j];
            count++;
        }
    }
    
    // Sort by fraction value
    qsort(fractions, count, sizeof(Fraction), compare);
    
    // Return k-th smallest (1-indexed)
    result[0] = fractions[k - 1].num;
    result[1] = fractions[k - 1].den;
    
    free(fractions);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int arr[100];
    int n = 0;
    char *token = strtok(line + 1, ",]");
    while (token != NULL) {
        arr[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result[2];
    solution(arr, n, k, result);
    printf("[%d,%d]\n", result[0], result[1]);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² log n)

Generate n² fractions, then sort them in O(n² log n) time

⚠ Quadratic Growth

Space Complexity

O(n²)

Store all n² fractions in memory

⚠ Quadratic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Generate All Fractions and Sort — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler