Welcome to Subscribe On Youtube

786. K-th Smallest Prime Fraction

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

 

Example 1:

Input: arr = [1,2,3,5], k = 3
Output: [2,5]
Explanation: The fractions to be considered in sorted order are:
1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.
The third fraction is 2/5.

Example 2:

Input: arr = [1,7], k = 1
Output: [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

 

Follow up: Can you solve the problem with better than O(n2) complexity?

Solutions

• Java
• C++
• Python
• Go

• class Solution {
      public int[] kthSmallestPrimeFraction(int[] arr, int k) {
          int n = arr.length;
          Queue<Frac> pq = new PriorityQueue<>();
          for (int i = 1; i < n; i++) {
              pq.offer(new Frac(1, arr[i], 0, i));
          }
          for (int i = 1; i < k; i++) {
              Frac f = pq.poll();
              if (f.i + 1 < f.j) {
                  pq.offer(new Frac(arr[f.i + 1], arr[f.j], f.i + 1, f.j));
              }
          }
          Frac f = pq.peek();
          return new int[] {f.x, f.y};
      }
  
      static class Frac implements Comparable {
          int x, y, i, j;
  
          public Frac(int x, int y, int i, int j) {
              this.x = x;
              this.y = y;
              this.i = i;
              this.j = j;
          }
  
          @Override
          public int compareTo(Object o) {
              return x * ((Frac) o).y - ((Frac) o).x * y;
          }
      }
  }
  
  

• class Solution {
  public:
      vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
          using pii = pair<int, int>;
          int n = arr.size();
          auto cmp = [&](const pii& a, const pii& b) {
              return arr[a.first] * arr[b.second] > arr[b.first] * arr[a.second];
          };
          priority_queue<pii, vector<pii>, decltype(cmp)> pq(cmp);
          for (int i = 1; i < n; ++i) {
              pq.push({0, i});
          }
          for (int i = 1; i < k; ++i) {
              pii f = pq.top();
              pq.pop();
              if (f.first + 1 < f.second) {
                  pq.push({f.first + 1, f.second});
              }
          }
          return {arr[pq.top().first], arr[pq.top().second]};
      }
  };
  
  

• class Solution:
      def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
          h = [(1 / y, 0, j + 1) for j, y in enumerate(arr[1:])]
          heapify(h)
          for _ in range(k - 1):
              _, i, j = heappop(h)
              if i + 1 < j:
                  heappush(h, (arr[i + 1] / arr[j], i + 1, j))
          return [arr[h[0][1]], arr[h[0][2]]]
  
  

• type frac struct{ x, y, i, j int }
  type hp []frac
  
  func (a hp) Len() int           { return len(a) }
  func (a hp) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
  func (a hp) Less(i, j int) bool { return a[i].x*a[j].y < a[j].x*a[i].y }
  func (a *hp) Push(x any)        { *a = append(*a, x.(frac)) }
  func (a *hp) Pop() any          { l := len(*a); tmp := (*a)[l-1]; *a = (*a)[:l-1]; return tmp }
  
  func kthSmallestPrimeFraction(arr []int, k int) []int {
  	n := len(arr)
  	h := make(hp, 0, n-1)
  	for i := 1; i < n; i++ {
  		h = append(h, frac{1, arr[i], 0, i})
  	}
  	heap.Init(&h)
  	for i := 1; i < k; i++ {
  		f := heap.Pop(&h).(frac)
  		if f.i+1 < f.j {
  			heap.Push(&h, frac{arr[f.i+1], arr[f.j], f.i + 1, f.j})
  		}
  	}
  	return []int{h[0].x, h[0].y}
  }
  

All Problems

All Solutions