Minimize Max Distance to Gas Station
BloomBerg
PhonePeThe problem
Given a sorted array arr of size n, containing integer positions of n gas stations on the X-axis, and an integer k, place k new gas stations on the X-axis.
The new gas stations can be placed anywhere on the non-negative side of the X-axis, including non-integer positions.
Let dist be the maximum distance between adjacent gas stations after adding the k new gas stations.
Find the minimum value of dist.
Your answer will be accepted if it is within 1e-6 of the true value.
Input: n = 10, arr = [1, 2, 3, 4, 5, 6 ,7, 8, 9, 10], k = 10 Output: 0.50000 Explanation: One of the possible ways to place 10 gas stations is [1, 1.5, 2, 2.5, 3, 3.5, 4, 4.5, 5, 5.5, 6, 6.5, 7, 7.5, 8, 8.5, 9, 9.5, 10]. Thus the maximum difference between adjacent gas stations is 0.5. Hence, the value of dist is 0.5. It can be shown that there is no possible way to add 10 gas stations in such a way that the value of dist is lower than this.
**Input **: n = 10, arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 1 Output: 1.00000 Explanation:
- One of the possible ways to place 1 gas station is [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11].
- New Gas Station is at 11.
- Thus the maximum difference between adjacent gas stations is still 1.
- Hence, the value of dist is 1.
- It can be shown that there is no possible way to add 1 gas station in such a way that the value of dist is lower than this.
Input: n = 10, arr= [3, 6, 12, 19, 33, 44, 67, 72, 89, 95], k = 2
- 10 <= n <= 5000
- 0 <= arr[i] <= 109
- arr is sorted in a strictly increasing order
- 0 <= k <= 105
cpp
class Solution {
public:
long double minimiseMaxDistance(vector<int> &arr, int k) {
}
};java
class Solution {
public double minimiseMaxDistance(int[] arr, int k) {
}
}python
class Solution:
def minimiseMaxDistance(self, arr, k):javascript
class Solution {
minimiseMaxDistance(arr, k) {
}
}csharp
class Solution
{
public double MinimiseMaxDistance(List<int> arr, int k)
{
}
}go
func minimiseMaxDistance(arr []int, k int) float64 {
}Stuck? Show a way to structure it+
- 01Search the maximum allowed adjacent distance between zero and the largest original gap.
- 02For a candidate distance, count how many new stations each gap requires.
- 03Shrink the answer range when the total required stations is at most k.
- 04Stop when the precision tolerance is reached and use ceil for required stations.
Reference answer
Then expect these follow-ups
Why is feasibility monotonic in d?
Tests: binary-search proof
How would you construct the station positions?
Tests: solution reconstruction
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question