New Charging Stations

Hard

Charging stations stand along a straight highway; their positions are given in stations in increasing order. You must build extra more stations at any points of the highway, not necessarily at integer positions. Afterwards, look at the longest gap between two neighboring stations. Return the smallest possible length of that gap. Answers within 10⁻⁶ of the exact value are accepted.

Example 1

stations=[0, 10, 12], extra=4 → 1.9999994549380062

Four new stations cut the gap of length 10 into 5 pieces of 2, and the gap from 10 to 12 is already 2 long. The longest gap is 2.

Example 2

stations=[3, 4, 10], extra=1 → 2.9999995376783772

The single new station goes in the middle of the gap from 4 to 10, at 7: the gaps become 1, 3 and 3.

Example 3

stations=[0, 7, 9, 20], extra=2 → 5.499999389257937

Constraints

2 ≤ len(stations) ≤ 2000
0 ≤ stations[i] ≤ 10⁸, stations is strictly increasing
1 ≤ extra ≤ 10⁸

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search

Similar problems

Median Across Two Arrays Hard Minimum of a Shifted Array With Repeats Hard Frame Around an Ink Blot Hard Smaller Values to the Right Hard Window Sums Within a Band Hard

Input

stations=[0, 10, 12], extra=4

Expected

1.9999994549380062

Run checks the first 3 tests in your browser. Submit checks all 96 tests on the server, hidden ones included.