Array of random numbers with sum in given range?

Question

In C, how do I get an array of n numbers (each 0x00-0xFF in my case), of which the sum is within a given range 0..k?

The almost duplicate C++ multiple random numbers adding up to equal a certain number targets a specific sum, but in my case the sum can be anything between 0..k.

Answer 1

You need to specify what is the desired distribution of the random numbers.

If there are no further requirements, I would suggest one of the following:

---

(1)

• pick random number a[1] in interval 0 .. k
• pick random number a[2] in interval 0 .. k-a[1]
• pick random number a[3] in interval 0 .. k-a[1]-a[2]
• ...
• pick random number a[n] in interval 0 .. k-a[1]-a[2]-...-a[n-1]

If you have upper limit m on the range of the random number, use min(k-a[1]-... m) as upper bound of the interval.

Disadvantages: you will get a lot of small numbers and just a few big ones.

---

(2)

• pick n random numbers a[1], .., a[n] in interval 0 .. m, m being the upper limit
• s = a[1]+a[2]+...+a[n]
• multiply each a[i] by k/s (if integers are required, round down)

Disadvantages: It is unlikely to get large numbers this way. If integers are required, there will likely be a gap between the sum of numbers and k due to rounding error.

---

I think you get "nicer" numbers with option (2) but as stated above, it depends on the requirements.

Answer 2

Assuming k is less than 255 * n one solution is to assign k / n to every element of the array, then randomly subtract a value to the array elements.

// for (int i = 0; i < n; i++) array[i] = k / n;
// for (int i = 0; i < n; i++) array[i] -= randbetween(0, array[i]);
for (int i = 0; i < n; i++) array[i] = randbetween(0, k / n);

This has an expected sum of k / 2. By tweaking the randbetween() function you can change the probability of the resulting array sum.