PROBLEM LINKDIFFICULTYMEDIUM EXPLANATIONFirst try to solve the 1D version. You have N integer points marked on a number line, the point(s) that minimze the sum of the distances from all the points lie between the median points. In case, N is even, there are two median points. For example,for N = 4, and points {2,3,5,6} , we can easily calculate that {3,4,5} are the integer points that will minimize the sum of distances from all the other points in {2,3,5,6}. We can extend this to the 2D version. First thing to realize is that we can treat X and the Y coordinates independently of each other. Let A be the answer to solve the 1D version on X coordinates. Let B be the answer to solve the 1D version on Y coordinates. The final answer is simple A*B. SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 09 Nov '12, 15:51

Can someone prove the claim made for the 1D version of the problem? answered 19 Feb '13, 21:29

median has equal number of numbers on both of its side. so lets say x is your median point for n points. Moving it to left means subtracting n/2 from the sum at x. However you have made the point far from the right side n/2 points. So you add n/2 again. Plus it's possible that now more points exist in the right side. For example rrrxrrr. moving x to left means rrrxrrrr. As you see, now you are adding more to the optimal sum and subtracting less. It is clear why x is the optimal place to choose now. answered 26 Nov '14, 20:50

Proof for 1D version. Let us consider an arbitrary point X. Let there be L number of points to the left of point X and R number of points to the right of X. Now, if L > R, let us move our point X one step to the left at X1. Our new sum of distances will be oldsum + R  L. Note that RL is < 0 so the new sum of distances < oldsum. So as long as there are more points to the left of our current point than on the right, we can keep moving left and decrease our sum. The same logic can be applied when R > L. This will continue till R == L. The point where the number of points to the left is the same as the number of points to the right is called the median. Hence Proved. answered 12 Jul '15, 16:36
