We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

K-th Smallest Prime Fraction

Difficulty: Medium

Problem Description

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

Key Insights

  • The fractions formed by arr[i] / arr[j] for all i < j need to be evaluated.
  • The array is sorted which can help in efficiently finding the k-th smallest fraction.
  • A max-heap can be utilized to maintain the smallest fractions encountered.
  • The constraints allow for an efficient algorithm that avoids the naive O(n^2) complexity.

Space and Time Complexity

Time Complexity: O(k log k)
Space Complexity: O(k)

Solution

To solve the problem, we can utilize a max-heap to store the fractions in a way that keeps track of the k smallest fractions efficiently. We start by iterating through the array, calculating fractions by pairing 1 with each prime number, then subsequently pairing the next integers with all the prime numbers that follow. By using a max-heap, we can efficiently keep track of the smallest fractions and discard larger ones. Once we have processed k fractions, the top of the max-heap will give us the k-th smallest fraction.

Code Solutions

import heapq

def kthSmallestPrimeFraction(arr, k):
    max_heap = []
    n = len(arr)
    
    for j in range(1, n):
        for i in range(j):
            fraction = (arr[i], arr[j])  # Store the fraction as a tuple
            heapq.heappush(max_heap, fraction)
            if len(max_heap) > k:  # Maintain only k smallest fractions
                heapq.heappop(max_heap)
    
    return list(max_heap[0])  # Return the k-th smallest fraction
← Back to All Questions