## Complete Question

### Approach

Repeat the coordinates in x points array and y points array according to the numsPoint array.

x1 = Take median of all the x axis points.

y1 = Take median of all the y axis points.

### Solution

``````int cost(x, y, a, b) {
return (abs(x-a)+abs(y-b));
}
int greedy(vector<int> numpeople, vector<int> x, vector<int> y){
vector<int> xx, yy;
int ans = 0;
for(int i = 0 ; i < numpeople.size();i++){
int count = numpeople[i];
while(count--){
xx.push_back(x[i]);
yy.push_back(y[i]);
}
}

sort(xx.begin(), xx.end());
sort(yy.begin(), yy.end());
int mx, my;

mx = xx[xx.size() / 2];
my = yy[yy.size() / 2];

for(int i = 0; i < numpeople.size();  i++){
ans += numpeople[i] * cost(mx, my, x[i], y[i]);
}
return ans;
}``````

The solution is of O(n^2) time complexity.

1. Way_to_go

I think the complexity is O(n*p) where n is the number of city and p is the max people in a city

• Aryan Ganotra

I get your point but it can’t be less than O(nlogn) as sorting is included.

2. Babumoshai

It should be median not average, please correct the same.

• Aryan Ganotra

Yes. The code is correct. I have changed it to median in the theory.