UVa 10041

10041 - Vito's Family

• http://acm.uva.es/p/v100/10041.html

Summary

1D Geometric Median

Explanation

O(n²) brute force solution clocks at about 0.080s.
O(nlogn + n) solution where we sort the input and determine the sum of distance from each of the locations clocks at about 0.030s.
Another O(nlogn + n) solution is to sort the input array and determine the distance from median to all.

Input

2
2 2 4
3 2 4 6

Output

2
4