## Saturday, November 5, 2016

### Hacker Rank - Standard Deviation

Problem:

Analysis:

The standard deviation is defined to be $\frac{\sum{(x - \frac{\sum{x}}{N})^2}}{N}$ That would require us to compute mean in a round first and then another round to compute the value, which also imply we need to store the numbers, but here is a trick such that we do not need to do that.

$\begin{eqnarray} & & \frac{\sum{(x - \frac{\sum{x}}{N})^2}}{N} \\ &=& \frac{\sum{(x^2 - 2x\frac{\sum{x}}{N} + \left(\frac{\sum{x}}{N}\right)^2})}{N} \\ &=& \frac{\sum{x^2} - 2\frac{\sum{x}}{N}\sum{x} + \left(\frac{\sum{x}}{N}\right)^2\sum{1}}{N} \\ &=& \frac{\sum{x^2} - 2\frac{(\sum{x})^2}{N} + \frac{(\sum{x})^2}{N}}{N} \\ &=& \frac{\sum{x^2} - \frac{(\sum{x})^2}{N}}{N} \\ \end{eqnarray}$

Solution:

With the algebraic trick above, we can easily implement it with a single pass scanning of the input data without storing them!

Code:

#include "stdafx.h"

// https://www.hackerrank.com/challenges/s10-standard-deviation

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int HACKER_RANK_S10_STANDARD_DEVIATION()
{
int n;
cin >> n;
double ss = 0;
double s = 0;
for (int i = 0; i < n; i++)
{
double v;
cin >> v;
s += v;
ss += v * v;
}
cout << fixed << setprecision(1) << sqrt((ss - s * s/n)/n) << endl;
return 0;
}