How should I practice Number of Suitable Locations?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon online assessment problems in FastPrep.

Is Number of Suitable Locations associated with Amazon?

FastPrep tags this as a Amazon coding interview or online assessment practice problem when the problem catalog has that company context.

FastPrep

Problem · Sorting

Number of Suitable Locations

● MediumAmazonFULLTIMEOA

See Amazon hiring insights

Amazon has multiple delivery centers across the world, represented by a number line from -10^9 to 10^9. There are n delivery centers, the ith one located at position center[i].

A point x on the number line is called a suitable location for a warehouse if it is possible to bring all the products from every delivery center to that point with a total travel distance of no more than d. At any one time, products can be brought from one delivery center and placed at point x; bringing products from a center at center[i] requires traveling to the center and returning, contributing a distance of 2 * |x - center[i]|. Thus the total travel distance to gather all products at x is the sum of 2 * |x - center[i]| over all centers.

Only integer points x on the number line (with -10^9 <= x <= 10^9) are considered. Given the positions of the delivery centers and the maximum total travel distance d, return the number of integer points x for which the total travel distance is less than or equal to d.

Examples

01 · Example 1

center = [-2, 1, 0]
d = 8
return = 3

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

02 · Example 2

center = [2, 0, 3, -4]
d = 22
return = 5

The suitable locations are {-1, 0, 1, 2, 3}, giving a count of 5.

At x = -1: total distance is 2*|-1-2| + 2*|-1-0| + 2*|-1-3| + 2*|-1-(-4)| = 22 <= d.
At x = 0: total distance is 2*|0-2| + 2*|0-0| + 2*|0-3| + 2*|0-(-4)| = 18 <= d.
At x = 1: total distance is 2*|1-2| + 2*|1-0| + 2*|1-3| + 2*|1-(-4)| = 18 <= d.
At x = 2: total distance is 2*|2-2| + 2*|2-0| + 2*|2-3| + 2*|2-(-4)| = 18 <= d.
At x = 3: total distance is 2*|3-2| + 2*|3-0| + 2*|3-3| + 2*|3-(-4)| = 22 <= d.

Since there are 5 such points, the answer is 5.

03 · Example 3

center = [-3, 2, 2]
d = 8
return = 0

There are no suitable locations. For example, placing a warehouse at x = 2 gives a total distance of 2*|2-(-3)| + 2*|2-2| + 2*|2-2| = 10 > d. No integer point achieves a total distance of at most d = 8, so the answer is 0.

Constraints

1 <= n <= 10^5
-10^9 <= center[i] <= 10^9
0 <= d <= 10^9
Only integer locations x with -10^9 <= x <= 10^9 are counted.