In a little town there are n houses on the main street. This street runs along the x-axis and the coordinates of the houses are x1; x2; .. ; xn. You decided to open a candy shop and you want to ?nd the most pro?table coordinate xbest . The most pro?table coordinate will be one that minimizes the sum of the distances to every house. Give an O(n) algorithm that ?nds xbest such that distbest:= ∑i=1 to n|xbest - xi| is as small as possible.