The question requests that given a list of numbersyou calculate a value to
To get rid of the absolute value, we break the sum into two parts:
Letbe the number of elements in that are less then or equal to , and be the number of elements greater then . Then, the sum can be written:
Note thatand don't depend on so we can ignore them. Minimizing the original function is equivalent to minimizing:
is minimized when . This happens when is the median of .
Finding the median can be done in linear time using the Top K Partitioning Algorithm covered in lessons 16-18 of Unit 4.