Moving Average of All Numbers in Stream

Problem

Given a stream of numbers, calculate moving average

Similar problem - [Moving Average of Last N numbers in a Stream](moving-average-of-last-n-numbers-in-a-stream)

Examples

Example 1

Solution

Method 1 - Simple Maths

This is straightforward math. If we have seen a total of n numbers so far, and the current average is avg, when a new element is added, the new average can be calculated as avg = (n * avg + new_element) / (n + 1). Below is the pseudocode to compute the moving average of all numbers in a stream in O(1) time:

Code

Python

avg = 0;
n = 0;

def add(element):
  avg = (n*avg)/(n+1);
  n++;
end

def getAvg()
  return avg;
end

Java

class MovingAverage {
	// Prints average of a
	// stream of numbers
	 void add(int x) {
		sum += x;
		n++;
	}

	public double getAvg(int x) {
		return (((double) sum) / n);
	}
}

If we get array as stream:

nums = [....]; // number stream
List<Integer> ans = new LinkedList<>();
var mAvg = new MovingAverage();
for(int num: nums) {
	mAvg.add(num);
	ans.add(mAvg.getAvg());
}