Saturday, November 5, 2016

Hacker Rank - Standard Deviation

Problem:

Please find the problem here.

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;
}

No comments :

Post a Comment