Question about minimizing sum of remainders

Question

I have a set of integers $[_1, _2, _3,.. , _]$. A non-negative integer $D$, greater than a certain threshold, divides each $_$ and leaves remainder $_$, i.e., $_$ can be written as $r_i = (c_i$ mod D). For all these numbers in the set, I want to find a single value of $$ that minimizes the sum of remainders i.e. minimize $Σr_i$. N and $c_i$ can have values in tens of thousands.

I know brute-force approach is an option, I want to know if there's any more efficient algorithm possible.

Answer 1

For $D > max_{1\leqslant i \leqslant N}(r_i)$, you'll have that the sum of remainders is $\sum_{i=1}^N c_i$ anyway. Hence, you can brute-force a minimum like so :

C $:= max_{1\leqslant i \leqslant N}(r_i)$;
minimum_sofar := $\sum_{i=1}^N c_i$; best_sofar := threshold
for threshold$<$D$<$C:
{R $:=\sum_{i=1}^N c_i \% D$;
if R $<$ minimum_sofar then:
{ minimum_sofar := R;
best_sofar := D;} }

The answer is in best_sofar once it's over.

Answer 2

If brute force is not an option and you still need to guess the divisor and no further information is known about the numbers , take the smallest integer within the acceptable threshold as the divisor.