786. K-th Smallest Prime Fraction

Problem

A sorted list A contains 1, plus some number of primes. Then, for every p < q in the list, we consider the fraction p/q.

What is the K-th smallest fraction considered? Return your answer as an array of ints, where answer[0] = p and answer[1] = q.

Examples:

Input: A = [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, 2/3.
The third fraction is 2/5.

Input: A = [1, 7], K = 1
Output: [1, 7]

Note:

• A will have length between 2 and 2000.
• Each A[i] will be between 1 and 30000.
• K will be between 1 and A.length * (A.length - 1) / 2.

Problem Statement

A sorted list A contains 1 and some other primes. When p<q for every pair in the list, we can construct a fraction p/q.

So what is the k-th smallest fraction? Return your answer in the form of an integer array, where answer[0] = p and answer[1] = q.

Note:

• The length of A is in the range 2 — 2000.
• The value of each A[i] is in the range 1 —30000.
• K is in the range 1 — A.length * (A.length - 1) / 2

Solution

• Given a sorted array in ascending order whose elements are all primes, find the K-th smallest proper fraction formed by numbers in this array when all such fractions are sorted in ascending order.
• The brute-force solution for this problem is to enumerate all possible proper fractions, sort them in ascending order, and output the K-th smallest fraction. Note that when sorting, you cannot directly sort by float; you need to convert fractions into a structure of numerator and denominator for sorting.
• The optimal solution is binary search. Since proper fractions are all less than 1, the binary search range is [0,1]. For each mid found by binary search, we need to scan the array once to find the number of proper fractions smaller than mid. Also record the numerator and denominator of the largest proper fraction, dynamically maintaining the numerator and denominator of the largest proper fraction. If the number of proper fractions smaller than mid is less than K, take the right interval and continue binary search; if the number of proper fractions smaller than mid is greater than K, take the left interval and continue binary search. Until the number of proper fractions smaller than mid is exactly K, the numerator and denominator of the maintained largest proper fraction are the answer.
• This series of problems about finding the K-th smallest element in a sorted matrix includes: Problem 373, Problem 378, Problem 668, Problem 719, and Problem 786.

Code

package leetcode

import (
	"sort"
)

// Solution 1: Binary search
func kthSmallestPrimeFraction(A []int, K int) []int {
	low, high, n := 0.0, 1.0, len(A)
	// Since binary search is performed on decimals, we cannot terminate the loop with mid+1 and boundary checks as in an integer range
	// Therefore, end the loop here based on count
	for {
		mid, count, p, q, j := (high+low)/2.0, 0, 0, 1, 0
		for i := 0; i < n; i++ {
			for j < n && float64(A[i]) > float64(mid)*float64(A[j]) {
				j++
			}
			count += n - j
			if j < n && q*A[i] > p*A[j] {
				p = A[i]
				q = A[j]
			}
		}
		if count == K {
			return []int{p, q}
		} else if count < K {
			low = mid
		} else {
			high = mid
		}
	}
}

// Solution 2: Brute force, time complexity O(n^2)
func kthSmallestPrimeFraction1(A []int, K int) []int {
	if len(A) == 0 || (len(A)*(len(A)-1))/2 < K {
		return []int{}
	}
	fractions := []Fraction{}
	for i := 0; i < len(A); i++ {
		for j := i + 1; j < len(A); j++ {
			fractions = append(fractions, Fraction{molecule: A[i], denominator: A[j]})
		}
	}
	sort.Sort(SortByFraction(fractions))
	return []int{fractions[K-1].molecule, fractions[K-1].denominator}
}

// Fraction define
type Fraction struct {
	molecule    int
	denominator int
}

// SortByFraction define
type SortByFraction []Fraction

func (a SortByFraction) Len() int      { return len(a) }
func (a SortByFraction) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a SortByFraction) Less(i, j int) bool {
	return a[i].molecule*a[j].denominator < a[j].molecule*a[i].denominator
}