UVa 10041

From Algorithmist
Jump to navigation Jump to search

10041 - Vito's Family[edit]

Summary[edit]

1D Geometric Median

Explanation[edit]

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

Input[edit]

2
2 2 4
3 2 4 6

Output[edit]

2
4