Jun 112012
 

Given a stream of numbers (keep reading numbers from the keyboard). Write code to print the average at each point. For example: user is entering the numbers, at each point you should print the average of all the numbers entered till now, as shown below


numbers             Average
————        ————-
10                    10
10, 20                15
10, 20, 30            20
10, 20, 30, 40        25
10, 20, 30, 40, 50    30
…                   …
…                   …

Solution:

One brute force approach is to compute average at each time, when a number is entered. Each average calculation will be O(n). Hence the total time taken will be O(n2).

Better Approach:

When a new number is entered, we consider the previous average and compute the new average in constant time, i.e O(1).

Hence, at every point when a number is entered, we consider the previous average and calculate the new average in O(1) time.

// Prints average of a stream of numbers
 void streamAvg(double arr[], int n)
 {
    float avg = 0;
    for(int i = 0; i < n; i++)
    {
       avg = (avg * i + arr[i])/(i+1);

       printf("Average of %d numbers is %f \n", i+1, avg);
    }
 }

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)