Среднее арифметическое куууучи чисел

А в чём проблема? Сумма двух милллиардов int'ов поместится в long даже если они все равны максимальному значению. А уж если int'ы нормальные...

Так что смело суммируйте всё в long с детектированием переполнения. И делите на количество.

Всё ещё проще на самом деле...

1. Имеем последовательность чисел x1, x2, x3, x4, x5...
2. k=2; //количество чисел, текущий шаг
3. Находим среднее арифметическое первых двух чисел r=(x1+x2)/k.
4. Далее не будем постоянно считать суммы, а будем брать следующий множитель для следующего среднего арифметического: n=(k*r+x3)/((k+1)* r). //x3 естественно на каждом шаге меняется на следующий элемент
5. Следующее среднее арифметическое: r=r*n.
6. k=k+1
7. Повторяем шаги 4..6 для нужного числа чисел.

И еще проще на python без enumerate:

def get_mid(iterator):
  mid = 0
  num = 1
  for value in iterator:
    mid += (value - mid) / num
    num += 1
  return mid

Или другими словами: mid[n] = mid[n-1] + (x[n] - mid[n-1])/n

Предложу свой вариант.
Этот миллиард группируется в какой-то класс. Много объектов. Группируется так, чтобы сумма этой группы нечаянно не превыcила Integer.MAX_VALUE. В объект заносится сумма этих чисел и их количество. Сами числа уже не нужны. Далее вычисляется ср. арифметическое для этого объекта. Придётся создать много таких объектов-групп. После разбивания всех входных данных на эти объекты-группы, зная общую сумму и общее количество, делим - и всё.

Очень хорошо, если хоть кто-то понял мой алгоритм.

Страдает точность, но переполнение невозможно.

avg = 0;
for (int i = 0, n = 1; i < array.length; i++, n++)
    avg = avg * (1 - 1f / n) + (float) array[i] / n;
return avg;

А если нам не нужно добавлять новые элементы в среднее арифметическое, мы можем сразу делить каждый элемент на n.

avg = 0;
for (int i = 0; i < array.length; i++)
    avg += (float) array[i] / array.length;
return avg;