algoadvance

You are given a sorted list of numbers arr and two integers A and B. arr represents the list of prime numbers. You need to find the A/Bth smallest prime fraction. A prime fraction in this context is a fraction arr[i]/arr[j] where 0 <= i < j < arr.length.

Clarifying Questions

  1. Input Format:
    • Is the input list always sorted in ascending order?
      • Yes, it is.
    • Could there be duplicate primes in the list?
      • No, the list contains unique prime numbers only.
  2. Fraction Precision:
    • Do we need to consider floating-point precision for fractions?
      • No, since the result should be returned in the form of indices of the two primes forming the fraction.
  3. Range Constraints:
    • Is A/B a guaranteed valid fraction with respect to the list length?
      • Yes, you can assume that A and B are such that a valid fraction exists.

Strategy

  1. Generating Fractions:
    • Use a min-heap to generate and store prime fractions.
    • Start with the smallest possible fractions by pairing the first element arr[i] with every other element arr[j], initializing the heap.
  2. Heap Management:
    • For each fraction arr[i]/arr[j] in the min-heap, keep track of the indices.
    • Extract the smallest element from the heap K-1 times.
  3. Binary Search Optimization:
    • Alternatively, use binary search to find the k-th smallest fraction. Maintain a count of fractions less than a middle value to guide the search.

Implementation

import heapq

def kthSmallestPrimeFraction(arr, k):
    # Create a min-heap
    heap = []
    n = len(arr)
    
    # Initial population of heap with smallest fractions (first element paired with each other)
    for j in range(1, n):
        heapq.heappush(heap, (arr[0] / arr[j], 0, j))
    
    # Extract k-1 elements from the heap
    for _ in range(k - 1):
        fraction, i, j = heapq.heappop(heap)
        # If i can be incremented (staying within bounds), push the next fraction
        if i + 1 < j:
            heapq.heappush(heap, (arr[i + 1] / arr[j], i + 1, j))
    
    # The k-th smallest fraction
    fraction, i, j = heapq.heappop(heap)
    
    return [arr[i], arr[j]]

# Example usage
arr = [1, 2, 3, 5]
A = 3
B = 7
print(kthSmallestPrimeFraction(arr, A * B))  # Output: [2, 5]

Time Complexity

  1. Heap Approach:
    • Heap initialization: O(n) since we push n-1 elements initially.
    • Heap operations (push and pop): Each operation takes O(log n), and we do this k-1 times.
    • Overall time complexity: O(n + k log n)

This approach ensures that the solution is optimized for the problem constraints and efficiently finds the k-th smallest prime fraction.

Try our interview co-pilot at AlgoAdvance.com