# Put an array into bins

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.

• I think a few more test cases would be nice. Mar 27, 2018 at 20:08
• your code must run in linear time - I would find any algorithm who doesn't follow this naturally quite weird Mar 27, 2018 at 20:18
• @Uriel There is no limit to how weird code-golf answers can be :)
– user9206
Mar 27, 2018 at 21:19
• @Lembik Though in what way is disallowing such potential weird approaches beneficial to a code-golf challenge? Mar 27, 2018 at 23:07
• @JonathanFrech it’s just down to the preferences of the OP :)
– user9206
Mar 28, 2018 at 7:00

# APL (Dyalog), 19 bytes

{+/⍺(⌈⍺÷⍨≢⍵)⍴⍵,⍺⍴0}


Try it online!

We append b zeros to the array before reshaping it into equal parts of ⌈⍺÷⍨≢⍵ (⌈ length of L ÷ b ⌉) and summing them, as depicted in ,⍺⍴0, since any amount of blank spots (which are not part of the original array) larger than b - 1 would be filled with at least b - 1 elements from other chunks, which makes the balancing point of the last group at maximum b - 1 difference from the rest. We use b > b - 1 because it is code golf.

For example, L with 15 elements and b = 3 wouldn't be grouped as

x x x x x x
x x x x x x
x x x 0 0 0


but rather as (note how the rightmost 2 xs "fills in" the leftmost zeros)

x x x x x
x x x x x
x x x x x


while a 16 elements array would be filled with 2 (3 - 1) blank spots, like

x x x x x x
x x x x x x
x x x x 0 0


# Python 2, 65 bytes

f=lambda l,n:n and[sum(l[:len(l)/n+1])]+f(l[len(l)/n+1:],n-1)or[]


Try it online!

# R, 757170 63 bytes

function(L,b)colSums(matrix(L[1:(ceiling(sum(L|1)/b)*b)],,b),T)


Try it online!

This pads L with NA until the length is a multiple of b, then takes the column sums of L as a matrix with b columns, removing NA values.

Explaining as a stack-based language:

function(L,b){
(ceiling(sum(L|1)/b*b)  # push the next multiple of b >= length(L), call it X
1:..                      # push the range 1:X
L[..]                       # use this as an index into L. This forces L
# to be padded to length X with NA for missing values
matrix(..,,b)         # create a matrix with b columns, using L for values
# and proceeding down each column, so
# matrix(1:4,,2) would yield [[1,3],[2,4]]
colSums(.., na.rm = T)        # sum each column, removing NAs


• Very nice and quick! The rise of the R coder...
– user9206
Mar 27, 2018 at 19:44
• @Lembik I was lucky enough to have popped into TNB right in between you saying "I'm going to post this as a challenge" and you actually posting it. Mar 27, 2018 at 19:55
• Oh look "length[<-" will return too just like our favorite buddy "[<-". No bytes saved for less readability: function(L,b)colSums(matrix("length<-"(L,ceiling(length(L)/b)*b),,b),T)
– Vlo
Mar 27, 2018 at 20:46
• @Vlo no bytes saved for less readability is probably the motto of R golfing...although I suppose that sum(L|1) is a byte saved from length(L)! Mar 27, 2018 at 20:48

# MATL, 6 bytes

vi3$es  ### Explanation Consider input 4, [0,3,7,2,5,1] as an example. v % Vertically concatenate stack contents. Gives the empty array, [] % STACK: [] i % Input b % STACK: [], 4 % Implicitly input L at the bottom of the stack % STACK: [0,3,7,2,5,1], [], 4 3$e     % 3-input reshape. This reshapes L with [] rows and b columns, in
% column-major order (down, then across). [] here means that the
% number of rows is chosen as needed to give b columns. Padding
% with trailing zeros is applied if needed
% STACK: [0 7 5 0;
3 2 1 0]
s       % Sum of each column
% STACK: [3 9 6 0]
% Implicitly display

• This is the most impressive answer in my view.
– user9206
Mar 30, 2018 at 11:18

# Ruby, 54 53 bytes

Saved a byte thanks to @Kirill L.

->l,b{s=1.0*l.size/b;(1..b).map{l.shift(s.ceil).sum}}


Try it online!

• Nice, you can also save a byte by replacing *b by 1..b Mar 29, 2018 at 14:50
• @KirillL. Thanks. Hadn't even occurred to me. Mar 29, 2018 at 22:06

# C (gcc), 107 bytes

j,k,t,Q;f(A,l,b)int*A;{for(j=~0;b>++j;printf("%d,",t))for(t=k=0;(Q=!!(l%b)+l/b)>k;t+=Q<l?A[Q]:0)Q=k+++Q*j;}


Try it online!

l#0=[]
l#n|o<-length ldivn+1=sum(take o l):(drop o l)#(n-1)


Try it online!

• Doesn't seem to work for [1, 2, 3, 4, 5, 6] # 3. Mar 28, 2018 at 11:55

# Java 10, 9689 86 bytes

a->b->{int r[]=new int[b],i=0,n=a.length;for(;i<n;)r[i/((n+b-1)/b)]+=a[i++];return r;}


Try it online here.

Found a shorter way to write i/(n/b+(n%b==0?0:1) here: i/((n+b-1)/b)

Thanks to Olivier Grégoire for golfing 3 bytes.

Ungolfed version:

input -> bins -> { // input is int[] (original array), bins is int (number of bins)
int result[] = new int[bins], // resulting array, initialized with all 0
i = 0, // for iterating over the original array
n = a.length; // length of the original array
for(; i < n ;) // iterate over the original array
result[i / ((n + bins - 1) / bins)] += input[i++]; // add the element to the right bin; that's bin n/bins if bins divides n, floor(n/bins)+1 otherwise
return result;
}

• 86 bytes Mar 29, 2018 at 13:58
• @OlivierGrégoire Thanks! Mar 29, 2018 at 14:12

# Elixir, 98 bytes

fn l,b->Enum.map Enum.chunk(l++List.duplicate(0,b-1),round Float.ceil length(l)/b),&Enum.sum/1 end


Try it online!

The best Elixir has is splitting into parts with a length of n. And it cannot ceil division as integer very well, so we do float division, round it up. Unfortunately the only way to do this results in a float, so we round it again to an integer.

• Some of your outputs have the wrong length.
– user9206
Mar 27, 2018 at 21:32
• @Lembik fixed it.
– Okx
Mar 27, 2018 at 21:51

# Perl 6,  52 51  50 bytes

52 bytes: Test it

->\L,\b{L.rotor(:partial,ceiling L/b)[^b].map: &sum}


51 bytes: Test it

{@^a.rotor(:partial,ceiling @a/$^b)[^$b].map: &sum}


50 bytes: Try it

{map &sum,@^a.rotor(:partial,ceiling @a/$^b)[^$b]}


47 bytes non-competing Test it

{@^a.rotor(:partial,ceiling @a/$^b)[^$b]».sum}


It's non-competing as ».sum is allowed to do the calculations in parallel. So it may or may not be in linear time.

## Expanded:

{  # bare block with two placeholder parameters ｢@a｣ and ｢$b｣ map # for each sublist &sum, # find the sum @^a # declare and use first parameter .rotor( # break it into chunks :partial, # include trailing values that would be too few otherwise ceiling @a /$^b # the number of elements per chunk