# Compute cumulative means efficiently

Consider a sorted array of positive floating point numbers such as:

input = [0.22, 2.88, 6.35, 7.17, 9.15]


For each integer $$\i\$$ from 1 up to the last value in input rounded up, output the mean of all values less than $$\i\$$.

In this case the output should be:

[0.22 0.22 1.55 1.55 1.55 1.55 3.15 4.155 4.155 5.154 ]


If there is no value in the input less than $$\i\$$ you don't need to add anything to the output.

More examples: (output rounded to three decimal places)

input = [2.37, 4.15, 5.47, 6.64, 7.01, 8.87, 9.37]

output = [2.37 2.37 3.26 3.997 4.657 5.128 5.752 6.269]

input =  [2.22, 2.66]

output = [2.44]

input = [0.09, 0.09, 2.21, 3.64, 7.26, 7.58, 9]

output = [0.09, 0.09, 0.797, 1.508, 1.508, 1.508, 1.508, 3.478, 3.478]

input = [0.35, 2, 2.45, 3.71, 5.13, 9.0, 9.66]

output = [0.35, 0.35, 1.6, 2.128, 2.128, 2.728, 2.728, 2.728, 2.728, 4.614]


You can round your output to three decimals places or not as you choose.

Your code should run in linear time in the length of the output plus the length of the input

• As it stands the task is impossible because an input like [1,N] has fixed length 2 but can force arbitrarily many output values. Or am I missing something obvious? May 14, 2023 at 18:53
• @loopywalt yes, thank you. I have fixed it
– Simd
May 14, 2023 at 18:59
• Now, one can construct arbitrarily long inputs while keeping the length of the output fixed, precluding a linear time exact solution. One would need constant time random access to input elements and would have to use that input is sorted and limit output accuracy and getting it right would still be super tricky. Can you confirm that this is intended? May 14, 2023 at 19:38
• @LuisMendo imho it’s a much more interesting coding task if it has to be linear time. It’s pretty trivial otherwise. I am hoping for a Python solution as that is the language I did it in (badly).
– Simd
May 15, 2023 at 3:18
• Could you add some cases with integer valued floats in the input? Maybe one with a trailing integer and one with an integer in the middle. There are several answers right now that would produce incorrect results
– ovs
May 15, 2023 at 11:02

# APL(Dyalog Unicode), 19 20 bytes SBCS

Added 1 byte to fix handling of trailing integers.

(⌈¯2-/⌊,⊢/)⊢⍤/+\÷⍳⍤≢


Try it on APLgolf!

                       ⍝ n←≢input, m←≢output
+\÷⍳⍤≢   ⍝ Cumulative averages
⍳⍤≢   ⍝ Numbers from 1 to n    - O(n)
+\       ⍝ Cumulative sums        - O(n)
÷      ⍝ Elementwise division   - O(n)
⌈¯2-/⌊,⊢/             ⍝ Repeat counts
⊢/             ⍝ Last value             - O(1)
⌊                ⍝ Floor of each number   - O(n)
,               ⍝ Concatenate            - O(n)
¯2-/                 ⍝ Adjacent differences   - O(n)
⌈                     ⍝ Ceil (last difference) - O(n)
⊢⍤/         ⍝ Repeat cumulative averages by
⍝ counts on the left     - O(m+n)


I'm pretty sure I can replace ⍳⍤≢ by the grading (sorting indices) primitive ⍋ because sorting a sorted list will always be O(n), but I can't really prove that.

• Shouldn't the floor ⌊ be a ceil ⌈? [2.37,5] currently results in [2.370,2.370,2.370,3.685] instead of [2.370,2.370,3.685]. May 15, 2023 at 9:22
• @KevinCruijssen According to the latest comment on the OP the correct output for that case should be [2.370,2.370,2.370], which also seems to be supported by the rules: For each integer 𝑖 from 1 up to the last value in input rounded up, output the mean of all values less than 𝑖
– ovs
May 15, 2023 at 10:48
• @KevinCruijssen fixed, I think
– ovs
May 15, 2023 at 11:02
• Ah, I hadn't paid attention to the comments, but the less than $i$ indeed indicates your current outputs are correct. Your fix indeed seems to be correct. I also see the same results in my simpler second 05AB1E program without the [restricted-complexity] for your two new test cases with 5.00. I just fixed my first program by using: append ceil(max) to the list; floor each; forward differences (basically the same as your fix, but in slightly different order). May 15, 2023 at 13:30

# C (gcc), 91 100 95 bytes

i;n;f(a,l,s)float*a,s;{for(i=n=s=0;i<a[l-1]+1;n<l&&a[n]<i?s+=a[n++]:++i*n&&printf("%f ",s/n));}


Try it online!

## Explanation

$$\i \le \lceil x \rceil \iff i \lt x + 1 \qquad \forall \quad i \in \mathbb{Z} \quad \textrm{and} \quad x \in \mathbb{R}\$$

• You made it look very simple!
– Simd
May 15, 2023 at 3:08
• Can save one byte by passing the length directly and indexing instead.
– pan
May 15, 2023 at 18:55
• thanks @pan, I much prefer passing the length directly instead of the last element, but I'm not sure about passing length - 1.
– c--
May 15, 2023 at 22:25

# Jelly, 11 bytes

ĊṪṭḞIx@Ä÷JƊ


A monadic Link that accepts a sorted list of positive floats and yields a sorted list of floats - the cumulative averages without any leading zeros.

Try it online!

### How?

ĊṪṭḞIx@Ä÷JƊ - Link: sorted list of positive floats, A = [a,b,...,z]
(length(A)=n, ceil(A[n])-ceil(A[0])+1=m)
Ċ           - ceiling  - O(n) -> [ceil(a),ceil(b),...,ceil(z)]
Ṫ          - tail     - O(1) -> [ceil(z)]
ṭ         - tack     - O(1) -> [a,b,...,z,ceil(z)]
Ḟ        - floor    - O(n) -> [floor(a),...,floor(z),floor(ceil(z))]
I       - deltas   - O(n) -> [floor(b)-floor(a),...,floor(z)-floor(y),floor(ceil(z))-floor(z)]
Ä    -   sums   - O(n) -> [a,a+b,...,sum(A)]
J  -   range  - O(n) -> [1..n]
÷   -   divide - O(n) -> [a,(a+b)/2,(a+b+c)/3,...]
@     - with swapped arguments:
x      -   repeat - O(n+m) -> [a,..a,(a+b)/2,...,(a+b)/2,...,...,Total/N]


# Wolfram Language (Mathematica), 71 or 110 bytes

Reap[Do[t=Select[#,#<i&];If[t!={},Sow@Mean@t],{i,⌈Max@#⌉}]][[2,1]]&


Try it online!

I had doubts about the time linearity, but the tests show that it is linear:

Try it online!

And for this code, the linearity of time can be algorithmically proven:

(c=1;m=0;Reap[Do[If[#[[c]]<i,m=Mean@#[[;;c++]];Sow@m,If[m>0,Sow@m,c=Min[Length@#,c+1]]],{i,⌈Max@#⌉}]][[2,1]])&


Try it online!

• For your second code, are the four spaces in the front really necessary? What about the space in m =0? May 15, 2023 at 8:16
• @AidenChow, oops, thank you! May 15, 2023 at 9:24
• I suspect that the first function is not in linear time, unless Select has some hidden mathematica-mojo that allows it to avoid scanning the entire $N$-element list with each of the $M$-repetitions of the Do loop. May 15, 2023 at 20:15
• @erfink Yes, so there is another option. But I tested with Select, real time is really linear. This is due to the fact that Mathematica effectively caches both input and intermediate data. Caching algorithms are unfortunately not exactly known. May 16, 2023 at 16:19

# OCaml, 290 bytes

290 bytes, it can be golfed much more. Any suggestion would be appreciated.

Golfed version. Try it online!

let mean_lt_i arr=let max=ceil(List.hd(List.rev arr))in let rec helper arr sum count i=if i>max then[]else match arr with |[]->(sum/.count)::(helper[]sum count(i+.1.0))|h::t->if h<i then helper t(sum+.h)(count+.1.0)i else(sum/.count)::(helper arr sum count(i+.1.0))in helper arr 0.0 0.0 1.0


Ungolfed version. Try it online!

let mean_lt_i arr =
let max = ceil (List.hd (List.rev arr)) in
let rec helper arr sum count i =
if i > max then []
else match arr with
| [] -> (sum /. count)::(helper [] sum count (i +. 1.0))
| h::t -> if h < i then helper t (sum +. h) (count +. 1.0) i
else (sum /. count)::(helper arr sum count (i +. 1.0))
in helper arr 0.0 0.0 1.0

let _ =
let arr = [0.22; 2.88; 6.35; 7.17; 9.15] in
mean_lt_i arr |> List.iter (Printf.printf "%.3f ");
Printf.printf("\n");
let arr = [2.37; 4.15; 5.47; 6.64; 7.01; 8.87; 9.37] in
mean_lt_i arr |> List.iter (Printf.printf "%.3f ");


# 05AB1E, 18 bytes

Å»+}ā/I¤îªï¥øεи}˜


Port of @JonathanAllan's Jelly answer (but without the convenient $$\O(n)\$$ builtins..), so make sure to upvote him as well!

Explanation:

Å» }      # O(n)   Cumulative left-reduce the (implicit) input-list by:
+       # O(1)    Adding items together
ā     # O(1)   Push a list in the range [1,length] (without popping)
/    # O(n)   Divide the values at the same positions in the lists
I         # O(1)   Push the input-list again
¤        # O(1)   Push its last/maximum value (without popping the list)
î       # O(1)   Ceil that last value
ª      # O(1)   Append it to the list
ï     # O(n)   Floor each value in the list
¥    # O(n)   Get the forward differences of this list
ø         # O(n)   Pair the values of the two lists together
ε        # O(n)   Map over each value:
# O(1)    Pop and push the values of the pair to the stack
и      # O(n+m)  Repeat the value the count amount of times as list
}˜       # O(n)   After the map: flatten the list of lists
# O(1)   (after which the result is output implicitly)


Unfortunately 05AB1E lacks vectorized repeat and/or zip-with builtins, hence the use of øεи} (zip, map, and repeat separately). δиÅ\ would be 1 byte shorter for this snippet, but would make it quadratic instead of linear.

Without the , it could have been 10 bytes:

¤îLε‹ÏÅA}˜


Explanation:

¤         # Get the last/maximum value of the (implicit) input-list
î        # Ceil it
L       # Pop and push a list in the range [1, ceil(max)]
ε      # Map over each value:
‹     #  Check for each value in the (implicit) input-list whether it's smaller than
#  this value
Ï    #  Only keep the values of the (implicit) input-list where this is truthy
ÅA  #  Get the arithmetic mean of these remaining values
}˜     # After the map: flatten the list of lists
# (after which the result is output implicitly)

• @JonathanAllan Should be fixed I think (as always, I'm not sure.. I'm so bad when it comes to O-complexity based challenges -_-). May 16, 2023 at 7:16

# Awk, 817966 62 bytes:

{for(;g<int($1);g++)if(n)print(m);m+=($1-m)/++n}END{print(m)}

Try it here: https://www.jdoodle.com/ia/I4A

Takes as input (and outputs) a contiguous newline-separated list of numbers. Will take input with gaps if an initial regex is added to only accept lines with numbers. 2 bytes reduced with canny substitution for NR. 17 bytes reduced by squashing everything (updating g) into a loop with all unnecessary variables trimmed, giving a healthy side effect of reducing punctuation.

Degolfed:

# implicit init: n=0, m=0, g=0
{for(;             # golfy blank init
g<int($1); # bring old floor up to new (no-op if equal): g++) # print the current cumulative mean # conveniently the right number of times if(n) # just don't print on first entry print(m) # print cumulative mean ; # we can chain functions without semicolons?? how very golfy m+=($1-m)/++n}     # increment n and inline cumulative mean
END{print(m)}      # one last time, with feeling


Code is transparently linear in input size, taking advantage of the sorted-ness of the array.

• Welcome to Code Golf, and nice answer! May 18, 2023 at 1:57
• Very nice answer and language choice.
– Simd
May 18, 2023 at 6:05

# R, 67 57 bytes

\(i)c(na.omit(sapply(1:-(-max(i)%/%1),\(x)mean(i[i<x]))))


Attempt This Online!

(shaved off 10 thanks to @dominic-van-essen)

• Nice! You can shave-off a few bytes with a few little golfs like this... May 23, 2023 at 15:32
• ...and 3 more bytes if you don't mind giving an attribute to the output vector like this... May 23, 2023 at 15:32
• 1:(9.9+1) produces the same as 1:10 because as.integer() always rounds down and the default sequence is an integer sequence, so 1:max(i+1) saves a lot. May 24, 2023 at 0:00
• @JonathanCaroll - 1:max(i+1) is unfortunately not the same as 1:ceiling(max(i)) when max(i) is an integer, and will round-up incorrectly in this case. May 24, 2023 at 6:26
• Ah, I missed that - it does fail the test case that ends with 9. Reverted. May 24, 2023 at 23:47

# Wolfram Language(Mathematica), 196187 179 bytes

$$\\color{red}{\text{The code doesn't output correct results. Any help would be appreciated.}}\$$

Saved 17 bytes thanks to the comment of @erfink

Golfed version. Try it online!

Module[{s=0,n=0,o={},i=1,j=1,l=Length,a=AppendTo},While[j<=l@p&&i<=Ceiling@Last@p,If[p[[j]]<i,s+=p[[j]];n++;j++;o~a~N[s/n],If[l@o!=0,o~a~Last@o];i++];If[j<=l@p&&p[[j]]>=i,i++]];o]


Ungolfed version. Try it online!

calculateMeans[input_List] :=
Module[{max = Ceiling[Last[input]], sum = 0, n = 0, output = {}, i = 1, j = 1},
While[j <= Length[input] && i <= max,
If[input[[j]] < i,
sum += input[[j]];
n++;
j++;
AppendTo[output, N[sum/n]];
,
If[Length@output!=0,AppendTo[output, Last[output]]];
i++;
];
If[j <= Length[input] && input[[j]] >= i,
i++;
];
];
output
]

input = {0.22, 2.88, 6.35, 7.17, 9.15};
calculateMeans[input] //Print

input = {2.37, 4.15, 5.47, 6.64, 7.01, 8.87, 9.37};
calculateMeans[input] //Print

• I think you can save 9 (or more) bytes by saving a couple reused functions to single variable names, particularly l=Length and a=AppendTo per the tip at codegolf.stackexchange.com/a/24400/62273. E.g., Module[{max=Ceiling@Last@p,s=0,n=0,o={},i=1,j=1,l=Length,a=AppendTo},While[j<=l@p&&i<=max,If[p[[j]]<i,s+=p[[j]];n++;j++;o~a~N[s/n],If[l@o!=0,o~a~Last@o];i++];If[j<=l@p&&p[[j]]>=i,i++]];o] May 15, 2023 at 3:38
• Save 4 more bytes by giving max a single character name. Even better, max only ever gets used as the upper bound for the outer While loop, so we can save 7 bytes by just having i<=Ceiling@Last@p instead of i<=max. This in turn would allow you to do the same trick as the previous comment with Last May 15, 2023 at 20:06

# Python 3, 121 bytes

def f(a):
i=n=s=0
while i<a[-1]+1:
if n<len(a)and a[n]<i:s+=a[n];n+=1
else:i+=1;n>0and print(s/n, end=' ')
print()


Try it online!

This is just a python version of c--'s C solution.

• Welcome (back) to Code Golf and Coding Challenges, and nice answer! You should add a link to an online interpreter to run this code, such as Try it Online or Attempt This Online. May 18, 2023 at 3:59

y x=y x 0.0 1.0 0where y(x:z)s i n|x<i=y z(s+x)i(n+1)|0<1=y[]s i n++y(x:z)s(i+1.0)n;y[]s i n=[s/n|n>0]


Try it online!

# Haskell, 179 bytes, sorted input ≥0, O(n)

import Data.List
c v=d$map last$groupBy((.fst).(==).fst)$zip(floor<$>v)$zipWith(/)(scanl1(+)v)[1.0..] d w=concat$zipWith replicate((\z->zipWith(-)(tail z)z++[1])$fst<$>w)(snd<\$>w)


Try it online!

# SAS

Input data in SAS can be passed as a SAS data set (standard SAS data transporting structure) or as macrovariable (a text string).

Solution 1) is based on input in SAS data set. Solution 2) is based on input passed as a text string. Though the solution 2) is 3 bytes shorter, it is the 1) which probably is more "SAS way".

Solution 1)

# 122 bytes

Input: Input is a SAS dataset i containing variable x:

data i;
infile cards dsd;
input x @@;
cards;
0.22, 2.88, 6.35, 7.17, 9.15
;
run;


Code:

data a;merge i i(rename=(x=y) firstobs=2);s+x;a=s/_N_;do j=j to coalesce(y,ceil(x));if j>x then output;end;retain j 1;run;


data a;
merge
i
i(rename=(x=y) firstobs=2);

s+x;
a=s/_N_;

do j=j to coalesce(y,ceil(x));
if j>x then output;
end;
retain j 1;
run;


The solution utilise merge statement which reads dataset i and data set i starting from the second observation with variable x renamed to y. Effectively for each value of x the y variable contains the next value. Only for the last value of x value of y is missing.

Dataset a contains cumulative average in variable a (alongside source data).

Solution 2)

# 119 bytes

Input: Input is a text string passed by a macrovariable x:

%let x=0.22, 2.88, 6.35, 7.17, 9.15;


Code:

data;array d[999](&x);do i=1to ceil(max(of d:));do while(-d[j+1]>-i);j+1;s+d[j];end;a=s/(j<>1);if a then put a;end;run;


data;
array d[999] (&x);

do i=1 to ceil(max(of d:));
do while(-d[j+1]>-i);
j + 1;
s + d[j];
end;
a = s/(j<>1);

if a then put a;
end;
run;


Result of the processing is printed out in the SAS log with put a; statement.

If text string in macrovariable &x contains more than 999 elements this part: d[999] has to be properly adjusted (what extends length). But, up to 999999, it still is not worse than 1).

The array statement in SAS data step (in this context) should not be confused with arrays which are available for example in C. In this context the array d[999] (&x) means "create 999 variables named d1, d2, ..., d999 initiated with values from text string passed by macrovariable &x.

# Charcoal, 31 bytes

⊞θ⌈⌈θ≔⁰η≔⁰ζＦθ«≦⊕η≧⁺ιζＩＥ…ι§θη∕ζη


Try it online! Link is to verbose version of code. Explanation:

⊞θ⌈⌈θ


Push the ceiling of the largest element of the list to the list.

≔⁰η≔⁰ζ


Start with no elements so far with a running total of zero.

Ｆθ«


Loop over the elements.

≦⊕η≧⁺ιζ


Update the count and sum.

ＩＥ…ι§θη∕ζη


Output the current average for each new integer before the next value.

ＩＥΦＥ⊕⌈⌈θΦθ‹λιι∕ΣιＬι


Try it online! Link is to verbose version of code.

• @KevinCruijssen Huh, well, I think this works, and it's shorter too, so thanks!
– Neil
May 16, 2023 at 12:41

# Excel, 49 bytes

=TOCOL(AVERAGEIF(A:A,"<"&SEQUENCE(1+MAX(A:A))),2)


Input is vertical array beginning in cell A1.

• Can you show its output on the test examples? Also, are you sure it is linear time?
– Simd
May 14, 2023 at 19:46
– Simd
May 14, 2023 at 20:44
• @Simd Testing shows that it runs in linear time, as I would have expected. May 15, 2023 at 4:03
• What timings do you get for inputs of length 1000 and 10000?
– Simd
May 15, 2023 at 4:58
• Ah, so for a tenfold increase of input size, which would mean a tenfold increase of output size, you would nevertheless expect to see only a tenfold increase in run time, not a hundredfold increase? May 15, 2023 at 5:34

# Elixir, 138 bytes

Golfed version. Try it online!

def y([],s,_,n),do: if n>0,do: [s/n],else: []
def y([x|z]=list,s,i,n)do if x<i do y(z,s+x,i,n+1)else y([],s,i,n)++y(list,s,i+1.0,n)end end


Ungolfed version. Try it online!

defmodule Main do
def y([], s, _, n), do: if n > 0, do: [s/n], else: []
def y([x | z] = list, s, i, n) do
if x < i do
y(z, s + x, i, n + 1)
else
y([], s, i, n) ++ y(list, s, i + 1.0, n)
end
end

def main do
IO.inspect y([2.37, 4.15, 5.47, 6.64, 7.01, 8.87, 9.37], 0.0, 1.0, 0)
end
end

Main.main()


# Erlang(escript), 127 bytes

Golfed version. Try it online!

y([],S,_,N)when N>0->[S/N];y([],_,_,_)->[];y([X|Z]=List,S,I,N)->if X<I->y(Z,S+X,I,N+1);true->y([],S,I,N)++y(List,S,I+1.0,N)end.


Ungolfed version. Try it online!

-module(main).
-export([y/4, main/1]).

y([], S, _, N) when N > 0 -> [S / N];
y([], _, _, _) -> [];
y([X | Z] = List, S, I, N) ->
if X < I ->
y(Z, S + X, I, N + 1);
true ->
y([], S, I, N) ++ y(List, S, I + 1.0, N)
end.

main(_) ->
io:fwrite("~p~n", [y([0.35, 2, 2.45, 3.71, 5.13, 9.0, 9.66], 0.0, 1.0, 0)]).


# Racket, 204 bytes

Golfed version. Try it online!

(define (y lst s i n) (cond [(empty? lst) (if (> n 0) (list (/ s n)) '())] [else (let ([x (first lst)] [z (rest lst)]) (if (< x i) (y z (+ s x) i (+ n 1)) (append (y '() s i n) (y lst s (+ i 1.0) n))))]))


Ungolfed version. Try it online!

#lang racket

(define (y lst s i n)
(cond
[(empty? lst) (if (> n 0) (list (/ s n)) '())]
[else
(let ([x (first lst)]
[z (rest lst)])
(if (< x i)
(y z (+ s x) i (+ n 1))
(append (y '() s i n) (y lst s (+ i 1.0) n))))]))

(define (main)
(displayln (y '(0.35 2 2.45 3.71 5.13 9.0 9.66) 0.0 1.0 0)))

(main)
`