In this simple challenge you are given an input array L
of non-negative integers and a number of bins b
greater than 0 but no more than the length of L
. Your code must return a new array M
whose length is b
and which has binned the array L
. This is easiest explained with examples.
L = [1,0,5,1]
and b = 2
returns M = [1,6]
.
L = [0,3,7,2,5,1]
and b = 3
returns M = [3,9,6]
.
So far, so simple. However in this question b
doesn't necessarily have to divide len(L)
. In this case the last bin will just have fewer numbers to make it up.
Each bin except possibly the last one must have the same number of numbers contributing to its total. The last bin must have no more numbers contributing to it than the other bins. The last bin must have as many numbers contributing to it as possible subject to the other rules.
L = [0,3,7,2,5,1]
and b = 4
returns M = [3,9,6,0]
. M = [10,8,0,0]
is not an acceptable output as the third bin does not have the name number of numbers contributing to it as bins 1
and 2
.
L = [0,3,7,2,5]
and b = 2
returns M = [10,7]
. M = [3, 14]
is not an acceptable output as the last bin will have 3
elements contributing to it but the first has only 2
.
L = [1,1,1,1,1,1,1]
and b = 3
returns M = [3,3,1]
.
As a final rule, your code must run in linear time.
You may use any language or libraries you like and can assume the input is provided in any way you find convenient.
It turns out that there are some inputs which can't be solved. For example [1,1,1,1,1]
and b=4
. Your code can output whatever it likes for those inputs.
your code must run in linear time
- I would find any algorithm who doesn't follow this naturally quite weird \$\endgroup\$