algorithm - Limited space average computation -

let's have n integers, n can huge, each int guaranteed between 0 , cap m, m fits in signed 32-bit field.

if want compute average of these n integers, can't sum , divide them in same signed 32-bit space - numerator carries risk of overflow if n large. 1 solution problem use 64-bit fields computation, hold larger n, solution doesn't scale - if m large 64-bit integer instead, same problem arise.

does know of algorithm (preferably o(n)) can compute average of list of positive integers in same bit-space? without doing cheap using 2 integers simulate larger one.

supposing know m initially, can keep 2 variables, 1 answer far divided m, , other remainder.

for example, in c++:

int ans = 0, remainder = 0; (int i=0;i<n;i++) {   remainder += input[i]; // update remainder far   ans += remainder/n; // move can remainder ans   remainder%=n; // calculate what's left of remainder } 

at end of loop, answer found in ans, remainder in remainder (if need rounding method other truncation).

this example works maximum input number m+n fits in 32-bit int.

note should work positive , negative integers, because in c++, / operator division operator, , % remainder operator (not modulo operator).