For such constructive algorithm questions, especially of this type, there are several methods.
(N-1) elements have some fixed value, and we manipulate the last element. In this case, we can set all (N-1) elements to 0, and find the last element accordingly. We can easily do so as-
Let K= standard deviation, and M be mean, and x be last element of array.
Another possible solution is as follows. (This is author’s solution).
Basically check the corner of n = 1 separately.
Now, 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.
I solved this problem with the same method of putting all elements(except last one) equal to zero and finding the last element according to the equation. But I got wrong answer. Can anybody find what is wrong with my
What I did was if n was even I printed -sigma n/2 times and sigma n/2 times. This makes the mean 0 and std=sqrt(n*sigma^2/sigma) = sigma.
If n was odd (n=1 handled separately) print last element as 0 and (n-1)/2 elements as sigma * sqrt(n/n-1) and the remaining as (-1 * sigma* sqrt(n/n-1)). Again makes mean 0 and then the usual stuff.
Another possible Approach which was used by our team is as follows. This is different from all other approaches because in this case each number generated is distinct i.e. no two numbers are same.
Let us try to generate an Arithmetic Progression :
k, 2k, 3k, 4k,…,nk whose standard deviation is \sigma. where k is some real number.
The value of k can be derived in about 6-7 lines by solving the equation of Standard Deviation which is left as an exercise for the reader. ( )
For n=1 , denominator( for eqn of k) turns out to be zero which indicated “-1” for the case when n=1.
Sigma was from 1 to {10}^{5} as in constraints, so I was talking with respect to that. Also, please comment such one liners under appropriate answers- makes it easier to address things
Process 2 was my main incentive with coming with the problem. The idea is that you can achieve a particular standard deviation by just multiplying the values by a constant was really nice.
The error margin is 1e-2, way too less. So, not much to worry about precision issues in general. You can easily use binary search. You can use formula too, but that’s not a reason against not using binary search.
Perhaps you are right. For me, absolute error margin is always dicey when values are large. I feel its better safe than sorry. I think you have a valid point, but my point also came from a similar practice problem.
I remember a problem, the values were <= {10}^{14} though, and we required careful binary search so that answer comes in margin of 0.01 of absolute error. My usual binary search gave WA. [Actually, the modification was trivial- but still, I mean, no one will want to take a risk when a O(1) solution is available- under impression that plain formula usage will minimize error].