A field-engineering team is calibrating a rack of environmental sensors before a satellite launch. Each sensor currently reports a single integer reading. The calibration rig lets an engineer nudge any one sensor's reading up or down by any amount from 0 up to a fixed tolerance value k -- a different nudge may be chosen independently for every sensor, but no nudge may ever exceed k in magnitude (in either direction). After every sensor has been (optionally) recalibrated, the team wants to know the smallest possible gap between the highest reading and the lowest reading among all sensors, assuming every nudge is chosen optimally to minimize that gap.
Line 1: two integers n and k, separated by a space -- the number of sensors and the calibration tolerance (1 <= n <= 10000, 0 <= k <= 10000).
Line 2: n integers, the current readings of the sensors, separated by spaces (-10000 <= reading <= 10000).
Print a single integer: the minimum possible value of (maximum reading - minimum reading) after optimally nudging every sensor by at most k.
Example 1
Input
3 3 4 10 2
Expected
2
Explanation
Readings are 4, 10, and 2, with tolerance 3. Before calibration the gap is 10-2=8. Raising the reading of 2 by 3 (to 5), lowering the reading of 10 by 3 (to 7), and raising the reading of 4 by 1 (to 5) brings every sensor into the range [5,7], a gap of only 2. This is optimal, since the gap can never shrink below 8 - 2*3 = 2.
Example 2
Input
2 3 1 15
Expected
8
Explanation
Readings are 1 and 15 with tolerance 3. Raising 1 by 3 to 4 and lowering 15 by 3 to 12 gives a gap of 12-4=8, which is optimal since the gap can never shrink below (15-1) - 2*3 = 8.
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 →