kaleabasfaw2010's blog

By kaleabasfaw2010, history, 9 days ago, In English,

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:

Image

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?

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by kaleabasfaw2010 (previous revision, new revision, compare).

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :)