786. K-th Smallest Prime Fraction Medium

1/**
2 * [786] K-th Smallest Prime Fraction
3 *
4 * 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.
5 * For every i and j where 0 <= i < j < arr.length, we consider the fraction arr[i] / arr[j].
6 * Return the k^th smallest fraction considered. Return your answer as an array of integers of size 2, where answer[0] == arr[i] and answer[1] == arr[j].
7 *  
8 * Example 1:
9 * 
10 * Input: arr = [1,2,3,5], k = 3
11 * Output: [2,5]
12 * Explanation: The fractions to be considered in sorted order are:
13 * 1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.
14 * The third fraction is 2/5.
15 * 
16 * Example 2:
17 * 
18 * Input: arr = [1,7], k = 1
19 * Output: [1,7]
20 * 
21 *  
22 * Constraints:
23 * 
24 * 	2 <= arr.length <= 1000
25 * 	1 <= arr[i] <= 3 * 10^4
26 * 	arr[0] == 1
27 * 	arr[i] is a prime number for i > 0.
28 * 	All the numbers of arr are unique and sorted in strictly increasing order.
29 * 	1 <= k <= arr.length * (arr.length - 1) / 2
30 * 
31 *  
32 * Follow up: Can you solve the problem with better than O(n^2) complexity?
33 */
34pub struct Solution {}
35
36// problem: https://leetcode.com/problems/k-th-smallest-prime-fraction/
37// discuss: https://leetcode.com/problems/k-th-smallest-prime-fraction/discuss/?currentPage=1&orderBy=most_votes&query=
38
39// submission codes start here
40
41impl Solution {
42    pub fn kth_smallest_prime_fraction(arr: Vec<i32>, k: i32) -> Vec<i32> {
43        vec![]
44    }
45}
46
47// submission codes end
48
49#[cfg(test)]
50mod tests {
51    use super::*;
52
53    #[test]
54    fn test_786() {
55    }
56}
57