Problem from "Competitive Programmer’s Handbook" by Antti Laaksonen, Page 61.
The problem is to find x to minimum the sum of the equation below:
I thought the answer will be the mean on the number because if we plot the in a 1D number line, the mean will be somewhere middle of them, so the absolute difference of distance between each number and the mean can be minimized.
The book says it is the median.
Example [1, 2, 2, 6, 9]
The mean will be 19 / 5 = 3.8. The absolute difference is 13.8.
The median is 2 an the absolute difference is 12.
I know that this is the absolute sum not the just the sum. But the median is only limited to the element of the array. Why x should be the median instead of the mean? Can this be mathematically proved?
This can indeed be proved mathematically, but I won't go into that for now, gonna give you an intuitive idea why median is wrong.
Consider the example [1,2,10000000]. Now check if mean is better or median :)
Yes it can be proved mathematically that madian is the value but i cannot disprove that mean is not like in sorted array you start pairing the elements the elements one from start other from the end i.e. pair 0 element to n-1, 1 to n-2 and so on as we know for any such pair the minimum will be obtained for any value in between them applying this to all pairs provided no. of elements are even one can easily say that minimum will be obtained on the median only