Google OA 2024 - Min Square 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, You need to determine the optimal integer location X to build a dark store such that the sum of the squared distances from the dark store to each home is minimized. Specifically, you want to minimize the value of Σi=1,N(X - A[i]) * 2

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=6 gives the value of 69 which is the minimum among all the integer values of X. Thus, the answer is 6.