Google OA 2024 - Min Abs Zepto Distance

You are given N integers representing the locations of homes on a straight street (x-axis). The ith home is located at A[i], You need to determine the optimal integer location X to build a dark store such that the sum of the absolute distances from the dark store to each home is minimized Specifically, you want to minimize the value of Σi=1 to Ν |Χ-Α[i]|.

Task

Determine the location of X which minimizes the value of the function given in the question.

Input Format:

1. The first line contains a single integer T, which denotes the number of test cases.

2. For each test case:

• The first line contains an integer N.

• The second line contains N space-separated integers denoting the array A.

Output Format:

For each test case, print the value of  X which minimizes the value of the function given in the question.

Constraints:

1<= T <= 10
1<= N <= 10^5
1 <= A[i] <= 10^9

Example

N=4
A = [1,7,11,9,3]

Approach

For all the values of X, only X=7 gives the value of 16 which is the minimum among all the integer values of X.
Thus, the answer is 7