The “Minimize Max Distance to Gas Station” problem is a classic example of using binary search on real numbers (floating point search) to optimize distances. <\/p>\n\n\n\n
In this blog, we\u2019ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.<\/p>\n\n\n\n
Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n We have a horizontal number line. On that number line, we have gas stations <\/strong>at positions stations[0], stations[1], …, stations[n-1], where n <\/strong>is the size of the stations array. Now, we add k<\/strong> more gas stations so that d<\/strong>, the maximum distance between adjacent gas stations, is minimized. We have to find the smallest possible value of d. Find the answer exactly<\/strong> to 2 decimal places. Your Task:<\/strong> Constraint:<\/strong> Let\u2019s solve the problem in the most straightforward way:<\/p>\n\n\n\n This approach is easy to understand but not efficient for large inputs or high precision.<\/p>\n\n\n\n
\n\n\n\nProblem Statement<\/strong><\/h2>\n\n\n\n
Note<\/strong>: stations<\/code><\/strong> is in a strictly increasing<\/strong> order.<\/p>\n\n\n\nExample 1<\/strong><\/h3>\n\n\n\n
Input:\n<\/strong>n = 10\nstations[] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]\nk = 9\nOutput:<\/strong> 0.50\nExplanation: <\/strong>Each of the 9 stations can be added mid way between all the existing adjacent stations.<\/pre>\n\n\n\n
Example 2<\/strong><\/h3>\n\n\n\n
Input:\n<\/strong>n = 10\nstations[] =
[3, 6, 12, 19, 33, 44, 67, 72, 89, 95]<\/code>
k = 2
Output:<\/strong> 14.00
Explanation: <\/strong>Construction of gas stations at 8th(between 72 and 89) and 6th(between 44 and 67) locations.<\/pre>\n\n\n\n
You don’t need to read input or print anything. Your task is to complete the function findSmallestMaxDist() <\/strong>which takes a list of stations and integer k as inputs and returns the smallest possible value of d. Find the answer exactly<\/strong> to 2 decimal places.<\/p>\n\n\n\n
10 <= n <= 10000 <\/sup>
0 <= stations[i] <= 109 <\/sup>
0 <= k <= 105<\/sup><\/p>\n\n\n
\n\n\n\nBrute Force Solution (Try Every Possible Distance)<\/h2>\n\n\n\n
Intuition and Approach<\/h3>\n\n\n\n
\n
Start from a small distance (like 0.01) and increase by small steps up to the largest gap between stations.<\/li>\n\n\n\n
For each distance, check if you can add at most k<\/code> stations so that no gap is larger than this distance.<\/li>\n\n\n\n
The first distance for which placement is possible is our answer.<\/li>\n\n\n\n
We check every possible distance, so we\u2019re sure to find the smallest one that works.<\/li>\n<\/ol>\n\n\n\nCode Implementation<\/h3>\n\n\n\n