I was asked this question in on online test. So, this question is not possible to submit on some judge. But I found a similar question somewhere else. The question goes like this...
Problem
There are multiple delivery centers and delivery warehouses all over the world! The world is represented by a number line from -10⁹ to 10⁹. There are n delivery centers, with the i-th one at location center[i]. A location x is called a suitable location for a warehouse if it is possible to bring ALL the products to that point AND then return them to their original locations by traveling a distance of no more than d.
At any one time, products can be brought from one delivery center and placed at point x. Given the positions of n delivery centers, calculate the number of suitable locations in the world. That is, calculate the number of points x on the number line (-10⁹ ≤ x ≤ 10⁹) where the travel distance required to bring all the products to that point AND then return them to their original locations is less than or equal to d.
Note: The distance between point x and center[i] is |x — center[i]|, their absolute difference.
Sample test cases
Case 1:
n=3, arr = [0, 1, -2], d = 8
output = 3
Case 2:
n = 4, arr = [2, -4, 0, 3], d = 22
output = 5
Constraints
1 <= n <= 1e5
-1e9 <= arr[i] <= 1e9
0 <= d <= 1e15
Approach
This is the approach I tried. Here’s the idea in plain English:
We want to find a range of positions on the number line where the total travel distance from all the delivery centers to a warehouse is less than or equal to a given distance, called d.
Binary search for the smallest point (xmin): — We start by trying to find the smallest position, xmin, where the sum of the distances from all the delivery centers to xmin is less than or equal to D. — We calculate the total distance by summing the absolute differences between xmin and each delivery center. — If we find such a point xmin, it marks the left end of our range.
Binary search for the largest point (xmax): — Similarly, we look for the largest position, xmax, where the sum of the distances from all the delivery centers to xmax is less than or equal to D. — If we find such a point xmax, it marks the right end of our range.
Range of valid positions: — The positions between xmin and xmax (including both) are all valid locations for the warehouse where the total travel distance from the delivery centers is within the limit D.
By finding xmin and xmax, we define a range [xmin, xmax] on the number line, and every position within this range is a possible location for the warehouse. This range contains all the valid points where the travel distance requirement is satisfied.
Code
bool cal(vi arr, ll d, ll x){
ll sum = 0;
for(ll i:arr){
sum+=abs(x-i);
}
return (2*sum)<=d;
}
void solve(){
int n;
cin>>n;
vi arr(n);
cin>>arr;
ll d;
cin>>d;
// sort(all(arr));
ll l1 = -1e9, h1 = 1e9;
ll minx = h1;
while(l1<=h1){
ll m = (l1+h1)/2;
if(cal(arr, d, m)){
minx = min(minx, m);
h1=m-1;
}else{
l1 = m+1;
}
}
l1=-1e9, h1=1e9;
ll maxx = l1;
while(l1<=h1){
ll m = (l1+h1)/2;
if(cal(arr, d, m)){
maxx = max(m, maxx);
l1=m+1;
}else{
h1 = m-1;
}
}
if(maxx<minx)cout<<0;
else cout<<(maxx-minx+1);
}
Issue (asking help)
But then while submitting, I found out that approach fails on some test cases. I figured that it makes a "V", where before that minx, everything is false, after that maxx, everything is false. between them its true.
FFFFFFFFF......FFFTTTTT....TTTTFFFFFFF......FFFFFF
I have done binary search where there's only 1 inflexion point. How do I tackle this problem with two inflexion points? Is there no way rather than to have multiple if else of checks to see if we are in the right inflexion point or the left inflexion point? What if there were 3 inflexion points? How would we approach that?
