The question goes like this

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.

For example:

n=3, arr = [0, 1, -2], d = 8 output = 3

n = 4, arr = [2, -4, 0, 3], d = 22 output = 5

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.

1. 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.

1. 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.

1. 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.

This is the code I wrote ~~~~~ 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);

} ~~~~~