Problem
Given a stream of numbers, calculate moving average
Similar problem - Moving Average of Last N numbers in a Stream
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());
}