When reading time-series data, looking at the average of the last few points instead of each raw value smooths out noise. An average computed over a fixed-size window that slides one step at a time is called a moving average.

Implement moving_average(nums, k), which reports the mean of every window of size k across an array of numbers.

Input

nums = [1, 2, 3, 4, 5]
k = 3

• nums is a list of integers or floats. Negative values are allowed.
• k is an integer of at least 1.

Output

Return a list holding each window's mean, from left to right.

moving_average([1, 2, 3, 4, 5], 3)
# [2.0, 3.0, 4.0]

Sliding the window one step at a time:

• The first window is [1, 2, 3]. The sum is 6, so the mean is 2.0.
• One step over is [2, 3, 4]. The sum is 9, so the mean is 3.0.
• One more step is [3, 4, 5]. The sum is 12, so the mean is 4.0.
• Sliding again would run past the end of the array, so it stops here.

The result has length len(nums) - k + 1, which is 5 - 3 + 1 = 3 above.

Performance requirement

Do not call sum() again for each window. Traverse the array exactly once.

Here is how. Compute the first window's sum once. Each time the window slides, subtract the value leaving it and add the value entering it. In the example you start at 6, subtract 1 and add 4 to get 9, then subtract 2 and add 5 to get 12. The inside of a window is never re-added.

Re-summing each window costs the element count times the window size. With 100,000 elements and a window of 1,000 that is 100 million operations, and it shows up as a timeout.

Things to watch

1. Round each mean with round(x, 6), to six decimal places. This applies to every window, not only the first one.
2. If k is larger than the array, no window can be formed, so return an empty list.
3. If k equals the array length there is exactly one window, and the result has length 1.
4. If k is 1 each window holds a single element, so the result is the original array as floats.
5. An empty array returns an empty list.

Implement moving_average(nums, k).

• nums is a list of ints or floats.
• An empty array returns an empty list.