1912. Moving Average of a Stream

Numbers arrive one at a time. After each one, print the average of the last k values, or of all of them if fewer than k have arrived, to exactly two decimal places.

No window average in this problem lands exactly on a half at the third decimal place, so the rule for rounding a tie never arises and you may use whatever your language's two-decimal formatting does.

## What most people try first

Re-add the window on every arrival. It is the obvious reading of the question and it is O(k) per number, so 100000 arrivals with a window of 100000 cost about 10^10 additions. That is far too slow, and nothing about the answer required it.

## Keep the total, not the window

Maintain one running sum. On each arrival add the new value, and once the window is full subtract the value that has just left it:

``` k = 3, stream 1 10 3 5

arrive 1 total = 1 nothing has left 1 / 1 = 1.00 arrive 10 total = 11 nothing has left 11 / 2 = 5.50 arrive 3 total = 14 window now full 14 / 3 = 4.67 arrive 5 total = 14 + 5 - 1 = 18 the 1 has left 18 / 3 = 6.00 ```

Each step is two additions and one division whatever k is.

## Why it is correct

Let S(i) be the sum of the window ending at arrival i. The window ending at i and the window ending at i - 1 differ in exactly two positions once the window is full: value i has entered and value i - k has left. So S(i) = S(i - 1) + v(i) - v(i - k) is not an approximation, it is the difference of the two sets written out. Before the window fills, nothing has left yet, which is why the subtraction is guarded. The divisor is the number of values actually in the window, which is i + 1 until the window fills and k afterwards.

## The boundary that breaks a careless implementation

Two off-by-ones live here and each has its own test. Dividing by k always makes every early average too small, because the window is not yet full. Starting the subtraction at i >= k - 1 instead of i >= k evicts one arrival too soon, so the window is permanently one value short.

The third trap is the format. Every line carries exactly two decimals, so a whole number prints as 4.00 and a cancelled window prints as 0.00, never as 0 and never as -0.00.

## Overflow

This is the one place in this problem where the type matters. A value reaches 100000 in magnitude and the window holds up to 100000 of them, so the running total reaches 10^10. That does not fit in a signed 32 bit integer, whose largest value is 2147483647, so the total must be 64 bit. In JavaScript a plain number is exact below 2^53 and 10^10 is far below it, so no BigInt is needed there, but no bitwise operator may touch the total because that would truncate it to 32 bits.

## Cost

O(1) per arrival and O(n) in total, with O(k) memory if you keep the window, or O(n) if you simply index the input you already read. The judge cannot enforce the per-arrival bound, so the O(n * k) rebuild passes every declared test; at the stated limit it would be about 10^10 additions, which is the figure that makes the running total worth writing.

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ k ≤ 100000` - `-100000 ≤ value ≤ 100000` - Each arrival is handled in `O(1)`. - No window average lands exactly on a half at the third decimal place.