Leetcode Problem 786. K-th Smallest Prime Fraction

786. K-th Smallest Prime Fraction

Leetcode Solutions

Approach #: Binary Search

  1. Initialize lo to 0 and hi to 1, as the smallest fraction is greater than 0 and the largest is less than or equal to 1.
  2. While lo is less than hi, do the following: a. Calculate mi as the average of lo and hi. b. Initialize count to 0 and maxFraction to (0, 1). c. For each j from 1 to len(arr) - 1, find the largest i such that arr[i] / arr[j] < mi using a linear scan. d. Update count by adding i and update maxFraction if arr[i] / arr[j] is greater than the current maxFraction. e. If count is less than k, set lo to mi, otherwise set hi to mi.
  3. Return maxFraction as the answer.
UML Thumbnail

Approach #: Heap

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...