Kth Smallest Fraction

Kth Smallest Fraction selects the k-th smallest value among fractions of the form:

$$ \frac{A[i]}{A[j]} $$

where the array $A$ is sorted and:

$$ 0 \le i < j < n $$

This problem appears in number theory and ranking problems. Direct enumeration gives $O(n^2)$ fractions, which is too large.

Problem

Given a sorted array $A$ of positive integers and an integer $k$, return the k-th smallest fraction among all pairs $(i, j)$ with $i < j$.

Algorithm 1: Min Heap

Treat each denominator as a column. Start with the smallest numerator for each denominator.

kth_smallest_fraction(A, k):
    H = empty min heap

    for j from 1 to n - 1:
        push (A[0] / A[j], i=0, j) into H

    repeat k - 1 times:
        (value, i, j) = pop minimum from H

        if i + 1 < j:
            push (A[i + 1] / A[j], i + 1, j) into H

    return top of H

Algorithm 2: Binary Search on Value

Search for a value $x$ such that exactly $k$ fractions are less than or equal to $x$.

kth_smallest_fraction(A, k):
    low = 0.0
    high = 1.0

    while true:
        mid = (low + high) / 2

        count, best_num, best_den = count_less_equal(A, mid)

        if count == k:
            return (best_num, best_den)
        else if count < k:
            low = mid
        else:
            high = mid

Counting uses two pointers:

count_less_equal(A, x):
    count = 0
    best_num = 0
    best_den = 1

    j = 1

    for i from 0 to n - 2:
        while j < n and A[i] > x * A[j]:
            j = j + 1

        if j == n:
            break

        count = count + (n - j)

        if A[i] * best_den > best_num * A[j]:
            best_num = A[i]
            best_den = A[j]

    return count, best_num, best_den

Example

Let:

$$ A = [1, 2, 3, 5] $$

All fractions:

$$ \frac{1}{2}, \frac{1}{3}, \frac{1}{5}, \frac{2}{3}, \frac{2}{5}, \frac{3}{5} $$

Sorted:

$$ \frac{1}{5}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3} $$

For $k = 3$, the answer is:

$$ \frac{2}{5} $$

Correctness

In the heap method, each denominator generates a sorted sequence of fractions. The heap merges these sequences, always extracting the next smallest fraction.

In the binary search method, the predicate "number of fractions $\le x$ is at least $k$" is monotone. The counting step correctly counts valid pairs using the sorted structure.

Tracking the best fraction during counting ensures that the exact k-th fraction is returned.

Complexity

method	time	space
heap	$O(k \log n)$	$O(n)$
binary search	$O(n \log R)$	$O(1)$

Here $R$ is the precision range for floating point search.

When to Use

Use the heap method when $k$ is small. Use binary search when $n$ is large and $k$ may be large.

The binary search method avoids storing many candidates and gives strong performance for large inputs.

Implementation

import heapq

def kth_smallest_fraction(a, k):
    n = len(a)
    heap = []

    for j in range(1, n):
        heapq.heappush(heap, (a[0] / a[j], 0, j))

    for _ in range(k - 1):
        _, i, j = heapq.heappop(heap)
        if i + 1 < j:
            heapq.heappush(heap, (a[i + 1] / a[j], i + 1, j))

    _, i, j = heapq.heappop(heap)
    return a[i], a[j]

func KthSmallestFraction(a []int, k int) (int, int) {
	type Node struct {
		value float64
		i, j  int
	}

	h := &MinHeapFraction{}
	heap.Init(h)

	n := len(a)

	for j := 1; j < n; j++ {
		heap.Push(h, Node{float64(a[0]) / float64(a[j]), 0, j})
	}

	for t := 0; t < k-1; t++ {
		node := heap.Pop(h).(Node)
		i, j := node.i, node.j

		if i+1 < j {
			heap.Push(h, Node{float64(a[i+1]) / float64(a[j]), i + 1, j})
		}
	}

	node := heap.Pop(h).(Node)
	return a[node.i], a[node.j]
}