medium K-th Smallest Prime Fraction

Problem Statement

You are given a sorted list of numbers that includes the number 1 and unique prime numbers. You are also given an integer k.

For every pair of indexes i and j, where 0 <= i < j < arr.length, we consider the fraction arr[i] / arr[j].

Find the K-th smallest fraction from these pairs, and return this fraction as an array containing the numerator and the denominator.

Examples

Example 1

• Input: arr = [1, 3, 5], k = 3
• Output: [3, 5]
• Explanation: The fractions are 1/3, 1/5, and 3/5. The sorted order is 1/5, 1/3, and 3/5. The 3rd smallest fraction is 3/5.

Example 2

• Input: arr = [1, 3, 7, 11, 13], k = 5
• Output: [3, 11]
• Explanation: The fractions are 1/3, 1/7, 1/11, 1/13, 3/7, 3/11, 3/13, 7/11, 7/13, and 11/13. The sorted order is 1/13 < 1/11 < 1/7 < 3/13 < 3/11 < 1/3 < 3/7 < 7/13 < 7/11 < 11/13. The 5th smallest fraction is 3/13.

Example 3

• Input: arr = [1, 5, 7, 23], k = 2
• Output: [1, 7]
• Explanation: The fractions are 1/5, 1/7, 1/23, 5/7, 5/23, and 7/23. The sorted order is 1/23 < 1/7 < 1/5 < 5/23 < 7/23 < 5/7. The 2nd smallest fraction is 1/7.

Constraints:

• 2 <= arr.length <= 1000
• 1 <= arr[i] <= 3 * 104
• arr[0] == 1
• arr[i] is a prime number for i > 0.
• All the numbers of arr are unique and sorted in strictly increasing order.
• 1 <= k <= arr.length * (arr.length - 1) / 2

Solution

To solve this problem, we can use a min-heap (priority queue) to efficiently find the K-th smallest fraction. The heap will store fractions along with their indices in the array. By always pushing the next potential smallest fraction, we maintain an efficient way to access the K-th smallest fraction without sorting all possible fractions, which would be computationally expensive.

This approach ensures that we only consider the smallest fractions first and incrementally work our way up to the K-th smallest. The min-heap helps us keep track of the next smallest fraction to consider, ensuring that the algorithm is both efficient and straightforward.

Step-by-Step Algorithm

1. Initialize a min-heap to store fractions and their indices. The heap will use a comparator to keep the smallest fractions at the top.
2. Push initial fractions into the heap. For each element i from 0 to n-2, push the fraction (arr[i], arr[n-1]) into the heap.
3. Extract the smallest fraction from the heap K-1 times:
   • Pop the smallest fraction from the heap.
   • If frac[1] - 1 > frac[0], push the next fraction (frac[0], frac[1] - 1) into the heap.
4. Return the K-th smallest fraction. After K-1 extractions, the smallest fraction in the heap is the K-th smallest fraction.
5. Output the numerator and denominator of the K-th smallest fraction.

Algorithm Walkthrough

Input: arr = [1, 5, 7, 23], k = 2

1. Initial Fractions in Heap:

   • (1/23, indices 0,3)
   • (5/23, indices 1,3)
   • (7/23, indices 2,3)

2. First Extraction:

   • Extract smallest fraction: (1/23, indices 0,3)
   • Push next fraction: frac[1] - 1 > frac[0] = 3-1 > 0. So, push (1/7, indices 0,2) in the min-heap

3. Heap after first extraction:

   • (1/7, indices 0,2)
   • (5/23, indices 1,3)
   • (7/23, indices 2,3)

4. Second Extraction:

   • Extract smallest fraction: (1/7, indices 0,2)

5. Return [1, 7] as the 2nd smallest fraction.

Code

import java.util.PriorityQueue;

class Solution {

  public int[] kthSmallestPrimeFraction(int[] arr, int k) {
    // Min-heap to store fractions as pairs of indices
    PriorityQueue<int[]> heap = new PriorityQueue<>(
      (a, b) -> arr[a[0]] * arr[b[1]] - arr[b[0]] * arr[a[1]]
    );

    // Initialize the heap with the smallest fractions (arr[i] / arr[n-1])
    for (int i = 0; i < arr.length - 1; i++) {
      heap.offer(new int[] { i, arr.length - 1 });
    }

    // Extract the smallest fraction k-1 times
    for (int i = 0; i < k - 1; i++) {
      int[] frac = heap.poll();
      if (frac[1] - 1 > frac[0]) {
        heap.offer(new int[] { frac[0], frac[1] - 1 });
      }
    }

    // The k-th smallest fraction
    return new int[] { arr[heap.peek()[0]], arr[heap.peek()[1]] };
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    int[] arr1 = { 1, 3, 5 };
    int k1 = 3;
    int[] result1 = solution.kthSmallestPrimeFraction(arr1, k1);
    System.out.println("Result 1: [" + result1[0] + ", " + result1[1] + "]");

    // Example 2
    int[] arr2 = { 1, 3, 7, 11, 13 };
    int k2 = 5;
    int[] result2 = solution.kthSmallestPrimeFraction(arr2, k2);
    System.out.println("Result 2: [" + result2[0] + ", " + result2[1] + "]");

    // Example 3
    int[] arr3 = { 1, 5, 7, 23 };
    int k3 = 2;
    int[] result3 = solution.kthSmallestPrimeFraction(arr3, k3);
    System.out.println("Result 3: [" + result3[0] + ", " + result3[1] + "]");
  }
}

Complexity Analysis

Time Complexity

The primary operations in the algorithm are related to the min-heap:

1. Heap initialization: Adding ( n-1 ) elements to the heap, which takes time.
2. Heap operations: Each of the ( k-1 ) heap extractions and insertions takes time. This results in a total of ) time.

Combining these, the overall time complexity is .

Space Complexity

The space complexity is primarily due to the heap, which stores at most (n-1 ) elements. Thus, the space complexity is .