Split arrays of natural numbers according to a requirement -

i have 2 arrays {ai} , {bi} of natural numbers. sums of elements equal.

i need split each element of 2 arrays 3 natural numbers:

ai = a1i + a2i + a3i bi = b1i + b2i + b3i

such sum of elements of a1 equal sum of elements of b1 , same other pairs.

the important part forgot about:

each element a1_j, a2_j, a3_j should between a_j/3-2 , a_j/3+2 or @ least equal 1 of these numbers

each element b1_j, b2_j, b3_j should between b_j/3-2 , b_j/3+2 or @ least equal 1 of these numbers

so elements of arrays must split in equal parts

i more elegant solution calculating possible variant both arrays.

i more elegant solution calculating possible variant both arrays.

it should possible divide them sums of a1, a2 , a3 near third of a, , same b. easy make values exact third, that’s not possible natural numbers. have floor results (trivial) , distribute remainders uniformly on 3 arrays (manageable).

i don't know whether it’s solution, works in o(n) , intuition says hold invariants (though didn’t proof it):

n = 3 j=0 n     a[j] = {} x = 0 // rotating pointer next subarray in     part = floor(a[i] / n)     rest = a[i] % n     j=0 n          a[j][i] = part      // distribute rest on arrays, , rotate pointer     j=0 rest         a[x][i]++         x++  /* same b */ 

one formulate loop without division, distributing single units (1) of a[i] on a[x][i]s:

n = 3 j=0 n     a[j] = {}     k=0 |a|         a[j][i] = 0 x = 0 // rotating pointer next subarray in     // distribute rest on arrays, , rotate pointer     j=0 a[i]         a[x][i]++         x++