Google OA-11 2024

Problem Description

You are given N integers that represent the locations of homes along a straight street (on the x-axis). The i-th home is located at A[i]. Your goal is to find the optimal integer location X for building 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 to N)​ (X−A[i])^2

Task:
Determine the integer location X that minimizes the value of the function described above.

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.