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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

K-th Smallest Prime Fraction

Number: 802

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Microsoft, Pony.ai

Problem Description

Given a sorted array arr consisting of 1 and prime numbers, consider all fractions of the form arr[i] / arr[j] for 0 <= i < j < arr.length. The task is to find the k-th smallest fraction among these fractions and return it as an array of two integers [arr[i], arr[j]].

Key Insights

  • All fractions are less than 1 because the array is sorted and i < j.
  • A direct approach of listing all fractions leads to O(n²) complexity, which can be too slow.
  • Binary search can be applied over the range of possible fraction values (0 to 1) to count how many fractions are <= a given candidate value.
  • For a fixed candidate value x, using a two-pointer technique can efficiently count the number of valid fractions and also track the maximum fraction <= x.
  • Alternatively, a min-heap method can be used to generate fractions in order, but binary search provides improved performance under the given constraints.

Space and Time Complexity

Time Complexity: O(n * log(1/ε)) where n is the length of the array and ε is the precision factor used in binary search. Space Complexity: O(1) additional space (ignoring the input storage).

Solution

The idea is to use binary search on the real number interval (0, 1). In each iteration:

  1. Set a candidate fraction value mid.
  2. For each possible numerator index, count the number of fractions with that numerator that are less than or equal to mid.
  3. Use a two-pointer approach: for each numerator, move the denominator pointer so that arr[i]/arr[j] <= mid holds.
  4. Keep track of the fraction that is the largest among those less than or equal to mid.
  5. If the total count equals k, return this fraction; otherwise, adjust the search range accordingly.

This method avoids generating and sorting all fractions explicitly, reducing the algorithm from O(n²) behavior.

Code Solutions

# Python solution for K-th Smallest Prime Fraction

class Solution:
    def kthSmallestPrimeFraction(self, arr, k):
        n = len(arr)
        # Binary search limits for fraction values
        low, high = 0.0, 1.0
        # Variables to store the best fraction
        best_numer, best_denom = 0, 1
        
        # Iterate until the precision is met
        while high - low > 1e-9:
            mid = (low + high) / 2.0
            count = 0
            i = -1  # Start with no numerator chosen yet
            best_numer, best_denom = 0, 1
            
            # For every denominator index, try to find valid numerators
            for j in range(1, n):
                # Increase i as long as the fraction is less than or equal to mid
                while i + 1 < j and arr[i + 1] < arr[j] * mid:
                    i += 1
                count += (i + 1)
                # Check if the current candidate fraction is larger than best candidate seen so far
                if i >= 0 and best_numer * arr[j] < best_denom * arr[i]:
                    best_numer, best_denom = arr[i], arr[j]
            
            # Adjust binary search boundaries based on count
            if count < k:
                low = mid
            else:
                high = mid
        
        return [best_numer, best_denom]

# Example usage:
# sol = Solution()
# print(sol.kthSmallestPrimeFraction([1,2,3,5], 3))
← Back to All Questions