Q1) 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.