PROBLEM LINK:Author: Arkapravo Ghosh DIFFICULTY:EASY PREREQUISITES:Maths, Greedy, Binary Search PROBLEM:Given N numbers a_{1}, a_{2}, a_{3}, … , a_{N}, you need to find the value X such that the result of the expression (a_{1} – X)^{2} + (a_{2} – X)^{2} + (a_{3} – X)^{2} + … + (a_{N} – X)^{2} is minimum possible. If multiple answers are there, you need to output the maximum one. QUICK EXPLANATION:We can simplify the expression that we need to minimize. The expression can be written as (a_{1}^{2} + a_{2}^{2} + a_{3}^{2} + … + a_{N}^{2}) – 2X(a_{1} + a_{2} + a_{3} + … + a_{N}) + NX^{2}. We can denote the term (a_{1} + a_{2} + a_{3} + … + a_{N}) as S. Now applying calculus to find the minimum value of the equation, we get 2 S + 2 NX = 0. Hence X = S/N. If two values exist(ie. if X = .50), then we need to output the maximum one(i.e. ceil(X)). We can also solve this problem by applying binary search. We can see that for the given condition to be satisfied, the value of X should lie between the minimum value and the maximum value in the given array. So we can do a binary search in the range of the minimum value and maximum value and find the required result. Again we need to output the maximum one in case two values exist. EXPLANATION:The given expression can be written as (a_{1}^{2} + a_{2}^{2} + a_{3}^{2} + … + a_{N}^{2}) – 2 X (a_{1} + a_{2} + a_{3} + … + a_{N}) + N X^2(eq. 1). We can denote the term (a_{1} + a_{2} + a_{3} + … + a_{N}) as S. Now we apply calculus to find the minimum value of the equation. By differentiating, we get 2 S + 2 N X(eq. 2). Again differentiating eq. 2, we get 2* N which is > 0. Hence we get the minimum value of eq. 1 by solving eq 2. Now equating eq. 2 with 0, we get, X = S/N. If two values exist(ie. if X%1 = 0.50), then we need to output the maximum one(i.e. ceil(X)). We can also apply binary search as explained before. Here binary search will work because the value of X will lie between the minimum and maximum value, and also by intuition we can understand. AUTHOR'S AND EDITORIALIST'S SOLUTIONS:Author's and editorialist’s solution can be found here.
This question is marked "community wiki".
asked 25 Sep '18, 20:32
