A lab records n numeric readings. Consider every unordered pair of distinct positions (i, j) and its gap |a[i] - a[j]|. If all n * (n - 1) / 2 gaps are listed in non-decreasing order, print the k-th one (1-indexed).
Gaps of value 0 are allowed (they occur when two readings are equal) and count normally.
Line 1: an integer n, the number of readings.
Line 2: n space-separated integers, the readings.
Line 3: an integer k with 1 <= k <= n * (n - 1) / 2.
A single integer: the k-th smallest pairwise absolute difference.
Example 1
Input
4 1 3 6 10 2
Expected
3
Explanation
The six gaps sorted are 2, 3, 4, 5, 7, 9; the 2nd smallest is 3.
Example 2
Input
3 5 5 5 2
Expected
0
Explanation
All three pairs have gap 0, so the 2nd smallest gap is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →