PROBLEM LINK:
Author: Praveen Dhinwa
Testers: Jakub Safin
Editorialist: Praveen Dhinwa
DIFFICULTY:
simple
PREREQUISITES:
none, basic definition understanding
PROBLEM:
Given two integers n, \sigma. Find an array a of length n such that the standard deviation of this array is exactly \sigma.
SOLUTION
First we must check for the corner case for n = 1. For n = 1, the \sigma value will always be zero. So, if n = 1 and \sigma \neq 0, output -1.
Now, we will consider only the cases n > 1.
Obtain standard deviation of 1 and then multiply the entries by \sigma.
If every element of an array of standard deviation \sigma is multiplied by an element p, then the standard deviation of the new array will be \sigma \cdot p.
So, you find an array of standard deviation 1, and multiply each of its entries by \sigma to obtain the desired standard deviation.
Let us create an array such that it has its mean 0 and almost all the values have a_i = 1, so the variance would be 1. In the case when n is even, then keeping half 1’s and the half -1’s does the job.
Consider the case when n is odd. This is bit tricky case. Here you have to keep (n-1)/2 1’s and -1’s, let the remaining three numbers be x, y, z. We want x+y+z = 0 and x^2 + y^2 + z^2 = 3. Simplifying, we get z = -(x+y).
Now, we make the further assumption that what if x = y.
We have z = -2*x, Solving eqs, x^2 = 0.5 \implies x = \sqrt(0.5), y = sqrt(0.5) and z=-2\times \sqrt(0.5)
You can see a sample implementation of this idea here
Binary search based solution
Let us fix the first n - 1 elements to be all zeros, and notice that if we increase n-th element from 0 to 10^8, the value of standard deviation will only increase. So, we use binary search over the last element to find out the desired \sigma. Note that problem is quite relaxed in terms of the errors, so a good implementation of this approach should pass without any issues. You can refer to the following code for a sample implemention
A slightly interesting random solution
First, we take an array of small numbers such that not all of them are equal, that’s the standard deviation is not zero. For example, let us take the array with half 1’s and half 2’s. You can even fill the array randomly with small numbers. Now, we find the standard deviation d of the array. Now, we multiply all the entries of the array by \frac{\sigma}{d} to obtain a standard deviation of \sigma.
#transhmaster’s solution idea
Let the standard deviation be denoted by \sigma and mean denoted by \mu.
According to the formula given in the problem :
\sigma^2 = \sum\limits_{i=1}^{n} \frac{{x_i-\mu}^2}{n}
n * \sigma^2 = \sum\limits_{i=1}^{n} {x_i-\mu}^2
If we take the \mu = 0, the equation reduces to
n * \sigma^2 = \sum\limits_{i=1}^{n} {x_i}^2
For making \mu = 0, we can have \frac{n}{2} positive numbers and another \frac{n}{2} additive inverses.
We can simplify it even further. What if we have a number x and its additive inverse -x in the array and all the rest of numbers are 0. By doing this, \mu still remains 0.
And our equation becomes
n * {\sigma}^2 = (x)^2 + {-x}^2
n* {\sigma}^2 = 2 x^2)
x^2 = n * \frac{sigma^2}{2}
x = \sqrt{n * \frac{sigma^2}{2}}
So now you have the value of x. Print x, -x and the rest of numbers are 0's.
#vijju123’s solution idea
We decide to have the first n-1 elements have some fixed value and we manipulate the last element. For example, we can set each of the first n-1 elements to 0, and find the last element accordingly.
We can easily do so as follows-
Let x be last element of the array.
We have
We have \mu = \frac{0 + 0 + 0 + \dots + x}{n} = \frac{x}{n}.
Hence,
Upon simplifying and solving this equation, you get