### code_stacker's blog

By code_stacker, history, 6 weeks ago,

Try solving for some p q r (sorted order). Think of them as points on the coordinate axis. What's the problem asking you to do? It's about finding a point such that sum of absolute differences between each pair of points is minimized. If you choose q to be that point, the answer is (q — p) + (r — q) + (q — q). If you choose some other point, let's say q + x for any value x, then the answer is ((q + x) — p) + (r — (q + x)) + (q + x — q) == (q — p) + (r — q) + x. Hence, the optimal point must be q.

Try solving for some case p q r s and notice that any value x satisfying q <= x <= r works. After solving these two cases, it's easy to show that median works.

Case 1: if n is odd arr {p,q,r,s,t} smallest summary distance = (s+t)-(p+q) Case 2: if n is even arr {p,q,r,s} smallest summary distance = (s+t)-(p+q) //can take any point from [q,r] all give same and min summary distance

• +6

 » 6 weeks ago, # |   0 Auto comment: topic has been updated by code_stacker (previous revision, new revision, compare).
 » 6 weeks ago, # | ← Rev. 2 →   +3 You are trying to minimize $f(x) = |x-a_1|+|x-a_2|+...+|x-a_n|$Consider $f'(x) = \frac{x-a_1}{|x-a_1|}+\frac{x-a_2}{|x-a_2|}+...+\frac{x-a_n}{|x-a_n|}$Using calculus, $f(x)$ is minimized at $x=x^*$, where $f'(x^*)=0$Solving for $f'(x^*)=0$ we get $x^*=a_\frac{n}{2}$ if $n$ is ODD and $x=\frac{1}{2}(a_\frac{n}{2}+a_{\frac{n}{2}+1})$ if $n$ is EVEN.This is exactly the definition of median of {$a_i$}$_{i=1}^n$
 » 6 weeks ago, # |   0 Auto comment: topic has been updated by code_stacker (previous revision, new revision, compare).