Along a straight service road there are n candidate mounting posts at distinct integer positions. You must switch on exactly k of them as signal towers. To reduce interference you want the two closest active towers to be as far apart as possible.
Choose k of the positions so that the minimum distance between any two chosen positions is maximized, and print that maximized minimum distance.
Line 1: an integer n, the number of candidate positions.
Line 2: n space-separated distinct integers, the positions (in any order).
Line 3: an integer k, the number of towers to switch on.
A single integer: the largest achievable minimum distance between chosen towers.
Example 1
Input
5 1 2 8 4 9 3
Expected
3
Explanation
Sorted positions are 1 2 4 8 9. Choosing 1, 4, 8 gives gaps 3 and 4, so the minimum is 3; no choice of 3 towers achieves a minimum gap of 4.
Example 2
Input
2 5 17 2
Expected
12
Explanation
With only two towers you must use both posts, and their distance is 12.
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 →