calculating previous k-average Given a number flow  $a_1, a_2, ... a_N$, $N$ is a large number for example $N = 1000$, the goal is to calculate the average value of previous $n$. For example, now we are at state $k$, then if $n = 20$ then $Avg(k) = (a_k + a_{k-1} + ... + a_{k-19})/20$, $k \ge 20$. 
1) given an equation to calculate this $Avg(k)$
My answer: $Avg(k) = Avg(k-1) + (a_k - a_{k-n})/n$
2)  Calculate $Avg(k)$ without using substraction
My answer: build an array that has the $Avg(1), Avg(2) ... Avg(k)$, update each one for each step, but it has complexity of $O(Nn)$. Do anybody know an $O(N)$ algorithm for this?
 A: You can keep track of the previous 19 numbers (in a 20 element array), and sum them with the current number, and the replace the oldest number in the array with the current one and move on. To compute the size-$n$ averages for all $N-n$ reasonable slots then takes time $O(Nn)$ as in your solution. 
But suppose that instead you keep track of the last 19 numbers, but also keep the sum of the last 1, the next 2, the next 4, the next 8, ... up to the largest power of 2 less than N. You move forward, and now you have the sum of the last 2, the next 2, the next 4, ...which you can update by keeping the last 2, but replaceing the next 2 with the sum of your first two elements, so that you have
last 2, next 4, next 4, next 8, ...
and you can cascade this. And you can tack on the last 1 to the first of the list. In log n time, you've updated this list. In log n time, you can compute the sum of more than half of the previous elements....but computing the sum for the remaining few still takes time O(n/2). But what if you kept a SECOND logarithmic list to help you do that bunch fast as well? Then you'd need to do at most $c * n/4$ work at the end. And so on....
In this manner, you keep $\log n$ lists, each of size $\log n$, and compute the sum in time that looks like (I think) $\log^2 n$, so your overall runtime ends up being $O(N \log^2 n)$. That's not $O(N)$, but it's a good deal better than $O(Nn)$. 
A: The solution for your first question is to keep track of the cumulative sum of the elements in a new array. Now when you are asked to find average of elements between say 'i' and 'j' indices, you can directly get the sum by of elements between these indices by subtracting cumulative sum of 'j' elements from cumulative sum of 'i' elements and divide it by n to get the average. In your case 'i' and 'j' are 'k-n' and 'k' respectively.
Now, time complexity for above algorithm is O(N), because you have to traverse the entire array once and build the cumulative sum array. And the space complexity is O(N), because you have to keep track of cumulative sum of all the elements.
Your second question can be solved by performing subtraction using bitwise operators. Here(https://www.geeksforgeeks.org/subtract-two-numbers-without-using-arithmetic-operators/) is the link to perform subtraction using bitwise operator. Any way time complexity and space complexity will not differ.
