Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Running sum of the last n integers in an array

Tags:

c

algorithm

Let's suppose that a process receives a new integer every 60 seconds. I would like to keep a running total of the last 5 numbers. For example:

3 1 99 10 8 0 7 9 --> running total is 10+8+0+7+9==34
       <--------->

Sixty seconds later, we receive a new integer. The list of received integers now looks like this:

3 1 99 10 8 0 7 9 2 --> running total is now 8+0+7+9+2==26
          <-------->

It's easy to implement this if you have storage space to save the last 5 integers. I'm trying to come up with an algorithm that's more memory efficient than that. Does anybody have any ideas?

like image 865
Andy Avatar asked Jul 29 '14 20:07

Andy


People also ask

What is running sum of an array?

The running sum of an array as rs[i] is sum of all elements from nums[0] to nums[i]. Finally return the entire running sum of nums.

How do you add all numbers in an array C++?

Step 1 : For i from 0 to n-1, follow step 2 ; Step 2 : sum = sum + arr[i] Step 3 : print sum.

Is sum possible in array?

For a given array, there can be many sum queries.


1 Answers

Since you can reconstruct the last n numbers, for example if you feed in n zeros, anything you do is equivalent to storing the last n numbers.

Assuming the numbers can be truly random and each number is b bits long, any correct algorithm can therefore exactly reproduce nb random bits. This requires at least nb bits of storage.

like image 174
Henry Avatar answered Oct 16 '22 15:10

Henry