×

# MNZEQ – Editorial

Author: Arkapravo Ghosh
Tester: Arkapravo Ghosh
Editorialist: Arkapravo Ghosh

EASY

# PREREQUISITES:

Maths, Greedy, Binary Search

# PROBLEM:

Given N numbers a1, a2, a3, … , aN, you need to find the value X such that the result of the expression (a1 – X)2 + (a2 – X)2 + (a3 – X)2 + … + (aN – 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 (a12 + a22 + a32 + … + aN2) – 2X(a1 + a2 + a3 + … + aN) + NX2. We can denote the term (a1 + a2 + a3 + … + aN) 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 (a12 + a22 + a32 + … + aN2) – 2 X (a1 + a2 + a3 + … + aN) + N X^2(eq. 1). We can denote the term (a1 + a2 + a3 + … + aN) 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".

3236
accept rate: 21%

19.6k349497539

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×992
×969
×860
×75
×75
×3