✍️ Feel free to see the Image Source section at the very bottom of the page for the original problem statement 🐘
Amazon, with its vast network of delivery centers scattered across the globe, operates on a massive number line stretching from -10⁹ to 10⁹. Imagine each center as a beacon along this number line, positioned at specific points known as center[i]. Now, Amazon is on a mission to find perfect warehouse spots, places where products from every delivery center can be gathered without exceeding a maximum travel distance, d. These warehouse spots, or "suitable locations," must be within reach of all delivery centers, ensuring that the total travel distance for bringing products to any one point doesn’t go beyond d. The task is to figure out how many such ideal locations exist on the number line, where the journey for all products is within this limit.
🌷 Can't thank engouth to the legendary GG of Error-Free Excellence - 🌟 spike 🌟! 🌷
Example 1:
Input: center = [-2, 1, 0], d = 8
Output: 3
Explanation:📝 ->> Check out the Image Source section at the bottom of the page for the original explanation 🐰Let’s imagine setting up the warehouse at x = -3. First, we bring products from the closest delivery center at center[0] = -2. The distance to bring the products to x = -3 is |-3 - (-2)| = 1, and then we return, covering another 1. Next, we move on to the products from centers 1 and 2, bringing them to x = -3. The total travel distance ends up being 1 + 1 + 4 + 4 + 3 + 3 = 16. Since this exceeds the maximum distance, d, this spot is not suitable for the warehouse.
Now, let’s try placing the warehouse at x = 0. The distance to bring products from center[0] = -2 is 2 * |0 - (-2)|, and from center[1] = 1, it’s 2 * |0 - 1|. Finally, the products from center[2] = 0 are already there, so the distance is 2 * |0 - 0|. Adding it all up, we get a total travel distance of 6, which is within the limit of d. So, x = 0 is a suitable location for the warehouse!
Let’s try placing the warehouse at x = -1 this time. To bring the products from center[0] = -2, the travel distance is 2 * |-1 - (-2)|. For center[1] = 1, it’s 2 * |-1 - 1|, and for center[2] = 0, the distance is 2 * |-1 - 0|. Adding everything together, the total distance is 8, which is within the limit of d. This makes x = -1 another suitable location for the warehouse!
Now, let's consider placing the warehouse at x = 1. To bring products from center[0] = -2, the travel distance is 2 * |1 - (-2)|. For center[1] = 1, the distance is 2 * |1 - 1|, and from center[2] = 0, it’s 2 * |1 - 0|. When we add it all up, the total distance traveled is 8, which is within the limit of d. So, x = 1 is also a suitable location for the warehouse!
The only suitable locations for the warehouse are x = -1, x = 0, and x = 1. Since there are 3 such spots, the total count of suitable locations is 3.
Example 2:
Input: center = [2, 0, 3, -4], d = 22
Output: 5
Explanation:📝 ->> Check out the Image Source section at the bottom of the page for the original explanation 🦋
Example 3:
Input: center = [-3, 2, 2], d = 8
Output: 0
Explanation:📝 ->> Check out the Image Source section at the bottom of the page for the original explanation 🐮
- 1 <= n <= 105
- -109 <= center[i] <= 109
- 0 <= d <= 1015
input:
output: