[Math] Split a number into n numbers

algorithms

I have to develop an algorithm that splits a number into n parts.

For example, if I have to split 12 in 3 numbers, I will have this: (4, 4, 4).

But if I have to split 11 in 3 numbers, I will have this: (4, 4, 3).

And 10 in 3 numbers, I will have: (4, 3, 3)

The different between the number and in the numbers split must be 0 or 1.

Is there any mathematical formula to do it?

Best Answer

To distribute the number $n$ into $p$ parts, you would calculate the “truncating integer division” of $n$ divided by $p$, and the corresponding remainder.

Mathematically that is (assuming that both $n$ and $p$ are strictly positive integers) $$ d = \left\lfloor \frac np \right\rfloor \, , \quad r = n \bmod p = n-pd \, . $$

In many programming languages you would do something like

int d = n / p; // truncating integer division
int r = n % p; // remainder

Then $$n = pd + r = r(d+1) + (p-r)d $$ so that the desired partition is $$ \underbrace{d+1, \ldots, d+1}_{r \text{ times}}, \underbrace{d, \ldots, d}_{p-r \text{ times}} $$

Related Question